Can someone please explain me how this type of recursion works?

Question

I came across this problem in recursion. I can't figure out how it works. I understand the basics of recursion but this totally confuses me. Please help.

main() { 
    foo(3); 
}

void foo(int x) {
    if (x >= 1) {
        foo(--x);
        printf("%d", x);
        foo(--x);
    }
}

I thought this program wouldn't print anything but it prints 0120 .

Doesn't the first call to foo(--3) i.e foo(2) jump to the beginning of the function and recur till 3 decrements to 0?

Please explain how this works.

Answer 1

The first call to foo() can be explained using a recursion tree:

  prints (in reverse order)

    2 <----------  foo(3)
                  /      \
    1 <----- foo(2)       foo(1) -----> 0
             /   \        /     \
    0 <-- foo(1) foo(0)  foo(0)  foo(-1)
         /    \ 
      foo(0)   foo(-1)

First, the left sub-tree will be evaluated and will print 012 and then the right sub-tree will be evaluated and will print 0. Finally you get the output:

0120

Answer 2

So foo(3) is:

foo(2)
print 2
foo(1)

And foo(2) is:

foo(1)
print 1
foo(0)

And foo(1) is:

foo(0)
print 0
foo(-1)

Now foo(0) and foo(-1) are no-ops, so foo(1) is:

print 0

Whence foo(2) is:

print 0
print 1

And foo(3) is:

print 0
print 1
print 2
print 0

This gives you the observed output.