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

Question

I ran into this problem in recursion. I can’t understand how this works. I understand the basics of recursion, but it totally bothers me. Please, help.

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

I thought this program does not print anything, but it prints 0120 .

Not the first call to foo (- 3) ie foo (2) goes to the beginning of the function and repeats up to 3 decrements to 0?

Please explain how this works.

Answer 1

The first call to foo() can be explained using the 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 subtree will be evaluated and will print 012 , and then the right subtree will be evaluated and will print 0 . Finally, you get the result:

 0120 

Answer 2

So foo (3):

 foo(2) print 2 foo(1) 

And foo (2):

 foo(1) print 1 foo(0) 

And foo (1):

 foo(0) print 0 foo(-1) 

Now foo (0) and foo (-1) are not op-ops, so foo (1):

 print 0 

Where does foo come from (2):

 print 0 print 1 

And foo (3):

 print 0 print 1 print 2 print 0 

This gives you the observed result.

Answer 3

this is the expected result. the following function calls are pushed onto the stack, and the printf command will not be executed until the previous function call returns.

 foo(3) --> foo(2) --> foo(1) --> foo(0) 

now x is not> = 1, so there are no more function calls and foo (0) is not popped from the stack. printf from foo (1) is executed and 0 (since the value of x has decreased) goes to stdout. another call to foo ():

 foo(3) --> foo(2) --> foo(1) --> foo(-1) // ^^ second foo() call from foo(1) 

current output:

 0 

it does nothing. foo (-1) and foo (1) are stacked.
now printf is called from foo (2) and 1 goes to stdout.

call foo (0).

 foo(3) --> foo(2) --> foo(0) // ^^ second foo() call from foo(2) 

current output:

 01 

foo (0) does nothing, then pop foo (0) and foo (2) the stack.

now we are in foo (3). type 2 and call foo (1).

 foo(3) --> foo(1) // ^^ second foo() call from foo(3) 

current output:

 012 

foo (1) calls foo (0), then prints 0, and then calls foo (-1). now all remaining foo are unloaded from the stack, and you get 0120 on exit.

@haccks - see this program. there are calls to foo (-1).

 #include <stdio.h> void foo(int); int main() { foo(3); return 0; } void foo(int x) { if (x >= 1) { printf("executing foo with x = %d\n",x-1); foo(--x); printf("original output: %d\n", x); printf("executing foo with x = %d\n",x-1); foo(--x); } } 

output:

 executing foo with x = 2 executing foo with x = 1 executing foo with x = 0 original output: 0 executing foo with x = -1 original output: 1 executing foo with x = 0 original output: 2 executing foo with x = 1 executing foo with x = 0 original output: 0 executing foo with x = -1