This recursive function puzzles me, what is going on?

Question

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 that happens at all.

int main()
{
        rec(10);
        return 0;
}

int rec(int n){
        if(n > 0)
                printf("%d\n", rec(n -1));
        return n;
}

Answer 1

The rec function on the printf line is evaluated before the printf itself. Thus the deepest instance of the rec function is printed first.

Answer 2

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);

Answer 3

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.

Answer 4

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?

Answer 5

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.

Answer 6

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.