Recursion order of outputs in C

Question

I have this recursive function in C,and i'm trying to understand why it's printing the way it does:

void rec(int x, int y){
 if (x == y) 
     return;
 rec(x--, y+1);
 printf("%3d%6.2f\n", x, (float) y);
}

I know that ther output for rec(8,4) is:

why the X value stays 7?as i understand it, the x-- should happen only after the line it's written.If not,why the value stays 7 and not decreasing? Also why the y value is decreasing?because it starts printing when the recursion is stopped?

I'm pretty new to C,and not used to all the little details that require attention(i'm coming from java)

thanks for any help!

For the `y` part, it's because you print *after* the recursive call, so the results will be printed in reverse order (last call first, first call last) — Federico klez Culloca, Aug 12 '19 at 09:09
Each recursive call creates its own `x` with no relation to any other (older) `x` — pmg, Aug 12 '19 at 09:11
It's like nested scopes: `{ int x = 10; { int x = -1; { int x = 42; /* x here is 42 */ } /* x here is -1 */ } /* x here is 10 */ }` — pmg, Aug 12 '19 at 09:15
please note that if you fix your code to be `rec(--x, ++y)` your code might never terminate because of for example: `rec(3,2) --> rec(2,3) --> rec(1,4) --> ...` — jaaq, Aug 12 '19 at 09:23

score 4 · Answer 1 · answered Aug 12 '19 at 09:12

For the y part, it's because you print after the recursive call, so the results will be printed in reverse order (last call first, first call last).

For the x part it's exactly because you're using post-decrement. When rec gets called it's passed the value it was passed before, and then it gets decremented. So you're always passing 8 to the recursive call, which then gets decremented and when the recursion ends it will finally print 7.

score 4 · Answer 2 · answered Aug 12 '19 at 09:16

When using the postfix decrement operator x--, the value of the expression is the value of the variable before the decrement is applied. That means that the value of x is only actually decremented in each call of rec after all of the child recursive calls are already done. That's why you see 7 printed at each step - each function does execute the decrement and prints it, but passes 8 to the child function.

However, if you were to prefix decrement operator --x, the value would be the value of the variable after the assignment was applied. This would give you the result you want, where the variable decrements with each recursive call. You could also do what you did for the y variable, and specify x - 1 rather than x--.

jaaq · Accepted Answer · 2019-08-12T09:29:36.303

This is not an issue of syntax but rather recursion and the call stack.

First off: doing rec(x--, y+1) passes the original value of x to the function and after the function is done, x is modified(but the modification is never saved). The same would happen to y if you passed it like this: rec(x--, y++). The "correct" way of doing it is changing the value before evaluating the function, as you did with y previously or like this: rec(--x, ++y).

Once you do this you will see that y is decreasing and x is increasing. Why? Because of the call stack. The function that is called last is will be done first. For this purpose you can imagine a calling a function as just copy pasting the code with the parameters already set. It would then look something like this:

void rec(int x, int y){
 if !(x == y) 
     rec(--x, ++y);

 printf("%3d%6.2f\n", x, (float) y);
}

...

if !(4 == 0){ 
     if !(3 == 1) 
          if !(2 == 2) 
              rec(--x, ++y);} // we are done now, no more "code is inserted"

          printf("%3d%6.2f\n", 2, (float) 2);

     printf("%3d%6.2f\n", 3, (float) 1);

printf("%3d%6.2f\n", 4, (float) 0);

score 3 · Answer 4 · answered Aug 12 '19 at 09:13

X: this is because you are using post-decrement in the rec call. What it does is first passing the current value of X to the call, then decrementing X:

rec(x--, y+1);

is equivalent to:

rec(x, y+1); x-=1;

Y: you print after the recursive call, so the first to print will be the "last" call made to rec, hence the one with the highest y value.

Recursion order of outputs in C

4 Answers4