The following program's output looks like this: n = 2 n = 1 n = 0 n = -1 n = 0 n = 1
I can follow through the program to the point where it prints out n = -1, but why does it go back up and prints n = 0 and n = 1 at the end?
#include <stdio.h>
void countdown (int n)
{
printf("n = %d\t", n);
n--;
if (n >= 0)
{
countdown(n);
}
printf("n = %d\t", n);
}
int main()
{
countdown(2);
return 0;
}
There are two printfs in the function, the last 3 printfs (n = -1 n = 0 n = 1) in your sequence
are printed by the second printf call, that's why it goes up again. You are forgetting about that one. When
the recursion ends, the function returns back to the previous level and continues
from there.
Eventually n-- is executed for n==0, n becomes negative, n >= 0 is evaluates
to false and countdown(n) is not executed any more. That's the terminal case.
That means that the function stops calling itself and continues and to the next statement which is the second
printf, which will print n = -1.
Then the function returns and the last and continues, which executes the second
printf and you get n = 0. Then the function ends and returns to the first
level, where the second printf is executed and you get n = 1. Then the
function returns back to main.
If you change the printfs a little bit in your recursion, you'll see
immediately why you get the output. Try this:
void countdown (int n)
{
printf("[1] n = %d\n", n);
n--;
if (n >= 0)
{
countdown(n);
}
printf("[2] n = %d\n", n);
}
Now the output will be
[1] n = 2
[1] n = 1
[1] n = 0
[2] n = -1
[2] n = 0
[2] n = 1
You have two printf statements being executed per call of the countdown function (one before and one after the recursive countdown() call).
It's a little hard to illustrate here, but let's look at how your countdown() function is being executed, and remember that in this case, the variable n is local to its associated function scope meaning that each occurrence of "n" within each countdown() function call is independent of the other.
countdown(2) <- spawns a new execution scope; let's call it S0
=> prints "n=2"
=> sets n=1 in scope S0
=> calls countdown(1) <- spawns a new execution scope; let's call it S1
----Inside S1----
=> prints "n=1"
=> sets n=0 in scope S1
=> calls countdown(0) <- spawns a new execution scope; let's call it S2
----Inside S2----
=> prints "n=0"
=> sets n=-1 in scope S2
=> if condition fails
=> prints "n=-1"
=> returns execution to scope S1
=> prints "n=0" (which is the value "n" has in scope S1)
=> returns execution to scope S0
=> prints "n=1" (which is the value "n" has in scope S0)
=> execution returns to main() function and program terminates
For n = 1 and n = 0, stack position is saved to go ahead where the function is stopped temporarily. After n=-1 case, the stack goes back from the saved positon. That's why you got n = 0 and n = 1 again with reversed-ordered. I recommend you to look at stack structure thereby grasping recursion logic.
