This recursive function puzzles me, what is going on?
I was playing around with recursion and did this simple function. I was assuming that it would print out 9-0 to stdout, but, it prints 0-9. I can't see how tha开发者_如何学JAVAt happens at all.
int main()
{
rec(10);
return 0;
}
int rec(int n){
if(n > 0)
printf("%d\n", rec(n -1));
return n;
}
The rec
function on the printf
line is evaluated before the printf
itself. Thus the deepest instance of the rec
function is printed first.
Think of it like this.
rec(10)
rec(9)
rec(8)
rec(7)
rec(6)
rec(5)
rec(4)
rec(3)
rec(2)
rec(1)
rec(0)
Start Unwinding
printf("%d\n", 0);
printf("%d\n", 1);
printf("%d\n", 2);
printf("%d\n", 3);
printf("%d\n", 4);
printf("%d\n", 5);
printf("%d\n", 6);
printf("%d\n", 7);
printf("%d\n", 8);
printf("%d\n", 9);
Let's rewrite your code like this:
int rec(int n){
if(n > 0)
{
int retval = rec(n -1);
printf("%d\n", retval);
}
return n;
}
Does it make it clear why 0 printed first before 9?
As Michael Burr says in the comments, if you want to see what's going on, compile with debugging symbols enabled, like this:
gcc -o test -g test.c
Then run with gdb like so.
gdb test
Then, to start things going, type
start
Which breaks at the first call in the main function. Type
step
to get to the next line in the code, and from then on, just press enter to keep repeating the last command. If you're happy, type continue
to stop stepping through. You'll see the values and evaluated lines at each stage which'll confirm the above answers.
Hope that provides some useful info.
Because you're creating 9 ambients 9 > 8 > 7 > 6 > 5 > 4> 3 > 2 > 1 > 0
, now these ambients are treated the same this would a(b(c(d(e(f(g()))))))
, going from the deepest one to the first one.
Remember that when you do this printf("%d",n(m));
you're actually not printing anything, you're saying "print the result of n(m)" then when it tries to resolve n(m) you're calling another print and saying once again "resolve n(m-1)".
Now, when you reach n(0) it will return 0 to be printed by the last call of printf
, therefore it prints 0 then 1 .. 9.
int main()
{
rec(10);
return 0;
}
int rec(int n){
if(n > 0)
printf("%d\n", rec(n -1));
return n;
}
In general, consider some piece of code. We say there is a direct relation between iterative and recursive solutions such that any solution can be written iteratively and vise versa. However, in some cases it is seen to be easier to express an algorithm recursively (eg. Tower of Hanoi.) In the case of the code above the equivalent would be the for loop construct.
This can be implemented as a function as follows:
void _for(int i, int n)
{
if( i >= n ) return; // TERMINAL<br />
// some expression (ie. printf("%d\n",i);)<br />
_for(i+1,n) // RECURSION<br />
}
Note, this can be extended using function pointers.
精彩评论