CODEWITHSUNDEEP
crecursion
lior
lior

Reputation: 152

Recursion order of outputs in C

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:

7 7.00
7 6.00
7 5.00
7 4.00

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!

Upvotes: 5

Views: 265

Answers (4)

jaaq
jaaq

Reputation: 1256

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

Upvotes: 4

Rob Streeting
Rob Streeting

Reputation: 1735

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--.

Upvotes: 4

Derlin
Derlin

Reputation: 9881

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.

Upvotes: 3

Federico klez Culloca
Federico klez Culloca

Reputation: 27119

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.

Upvotes: 4

Related Questions