Thread: this recursion behavior baffles me

Remember, the first call to a calls the next call to a. Therefore, when the next call to a returns, it returns to the first call to a, not to the main function. It is the first call to a that returns to the main function.

Ok, that makes sense but what is it that makes the compiler execute the remaining code 5 times. Is it because each call remains on the stack and that is how it knows how many times to execute remaining code?

Yes.

I would love to know the reasoning behind the function not exiting when the if statement returns false because the printf is within the if's block.

It does exit - but only when the escape condition is met - for all the other calls you are going 'down' another layer - like russian dolls, until you get to the call where x < 5 - then each call is exited succesively back to the original call which exits to main()


maybe this example helps to visualise it, the code used is purely for illustration, I dont recommend writing something this way! ... the opening braces of the while loop are analgous to the recursive calls going 'down' (as i picture it) until the recursion depth limit is met and then the closing braces represent the exits being met and coming back out of the stack

Code:

#include <stdio.h>

void CountDown(int x)
{
   while(x >= 5)
    {
        x -= 5;
        printf("%d\n", x);

        while(x >= 5)
        {
            x -= 5;
            printf("%d\n", x);

            while(x >= 5)
            {
                x -= 5;
                printf("%d\n", x);

                while(x >= 5)
                {
                    x -= 5;
                    printf("%d\n", x);

                    while(x >= 5)
                    {
                        x -= 5;
                        printf("%d\n", x);
                    }
                }
            }
        }
    }
}
int main()
{

    int x = 25;

    printf("%d\n", x);

    CountDown(x);

    return 0;
}

and then the function end brace

Ah - I think you have been using 'step' in the debugger - that's fine but with recursion it will kid you- you are at the closing brace.. but try using 'step into' when at the point of entry into the nested call - experiment with a breakpoint just on the call and then use step in - stuff like that - you should then be able to follow more exactly the flow

The strange thing is that 25, 20, 15, 10, 5, 0 passed during the recursive calls. The outputs prints out 5, 10, 15, 20, 25. I understand this is due to first in first out on the stack, but I dont understand why the printf doesnt output 5, 5, 5, 5, 5. There doesn't seem to any line of code which increments the value of x or a pointer to x, yet the value of x changes durring each iteration.

It is because you have put your recursive call before the printf(..) statement. - If you can understand the flow correctly, you will not escape to reach that point until the escape is reached, at which point 'that' function call exits to its calling point - and x will equal the local value of the frame it was called from - 5 - - then on the next escape up x will equal 10 which is what it was local to that call... etc

That in mind it kind of breaks my code example earlier - but i just wanted to show a visual code pattern more than the out commands. - If i had put the print statements after the closing braces of the loops it would have stood up though. - But now i cant edit post :-(

Originally Posted by generaltso78

The strange thing is that 25, 20, 15, 10, 5, 0 passed during the recursive calls. The outputs prints out 5, 10, 15, 20, 25. I understand this is due to first in first out on the stack, but I dont understand why the printf doesnt output 5, 5, 5, 5, 5. There doesn't seem to any line of code which increments the value of x or a pointer to x, yet the value of x changes durring each iteration.

The value of x isn't actually changing. Each call to a() creates its own variable called x (the parameter is passed by value, meaning the function gets a copy of what was provided to the function call). Each of the 6 calls to a() will have its own variable, with a separate value. Those values never actually change.

main() calls a with x = 25
a calls a with x = 20
a calls a with x = 15
a calls a with x = 10
a calls a with x = 5
a calls a with x = 0

The thing is, those are six different function calls and six different variables allocated. The sixth (deepest) function call doesn't print, it just returns control to the fifth call of a, which prints its value of x (5), then returns control to the fourth call of a, which prints its value of x (10), then returns control to the third call of a, etc., until eventually the first call of a prints its value of x (25) and returns control to main.

If you passed a pointer to x (and altered how you were decrementing x), then each of the 6 calls to a() would have their own pointers, but they would all point to the same data, and you'd print the same value five times.

Maybe your function would be easier to follow the flow onscreen if you print one message when you start and one message when you leave, something like

Code:

void a(int x) {
	printf("started a(%d)\n", x);
	if (x >= 5) {
		a(x-5);
	}
	printf("ended a(%d)\n", x);
}