CODEWITHSUNDEEP
crecursiondecrement
infinitloop
infinitloop

Reputation: 3011

How is this behaviour of C explained?

so I was playing around with recursion in C and I am not sure why is this happening:
code A

int foo(int x)
{
 if (x==0) return 0;
 else return foo(--x)+x;
}

int main() { printf("%d\n", foo(10));

code B

int foo(int x)
{
 if (x==0) return 0;
 else return foo(x--)+x;
}

int main() { printf("%d\n", foo(10));

Code A prints 45 instead of 55 and I figured that out. It is because the recursive call gets unwounded this way: 9+8+7+...+0 = 45

Code B on the other hand gets stuck and never returns to the prompt!! i have to ctrl+c it. Why does it get stuck? Is it because it never decrements past 10?

Upvotes: 2

Views: 192

Answers (5)

BlackBear
BlackBear

Reputation: 22979

That's because in snippet B x gets decremented after the recursive call so the function is always called with foo(10)

EDIT:
As James McNellis pointed out in its comment x gets decremented before calling the function but its original value is used in the call instead of the decremented one.
Basically the expression x-- is evaluated before foo(x--) but its value is actually x, therefore the function is called with x = 10

Upvotes: 9

James McNellis
James McNellis

Reputation: 355039

The value of the expression x-- is the current value of x, before the stored value is decremented. So, in calling foo(x--), the value of the argument to foo is always the same as its current value, yielding infinite recursion.

Note, however, that the behavior of both programs is potentially undefined, and depends on the order of evaluation of the subexpressions of foo(x--) + x and foo(--x) + x. Let's consider the first program, which contains the expression

foo(--x) + x

If the subexpressions are evaluated in the following (valid!) order, the program has undefined behavior:

  1. x is read to compute the value of the x as the right-hand side operand of +,

  2. x is read to compute the value of the x as an operand of --,

  3. x is written to store the new value of x after it is decremented

  4. foo is called

The only sequence point here is between steps 3 and 4: after the argument expression is evaluated, before the function is called. Because x is read twice (in [1] and [2]) and written once (in [3]) and because one of the reads (in [1]) is not for the purpose of computing the new value to be stored, the behavior is undefined.

Evaluation order is unspecified, but if this evaluation order is the order that is used, the program has undefined behavior.

The same reasoning applies equally to the second program.

It would be best to use x - 1 as the argument to foo, as this expression does not modify the value of x.

Upvotes: 1

T.W.R. Cole
T.W.R. Cole

Reputation: 4156

Post-decrement (x--) waits for the function call to return before executing. So your stack would look like:

foo(10)
foo(10)
foo(10)
...

Upvotes: 2

user529758
user529758

Reputation:

calling

foo(--x)

calls the function with the already decremented value, while

foo(x--)

always calls it with the original value (i. e. 10), so it never gets even close to zero, that's why.

Upvotes: 0

xQuare
xQuare

Reputation: 1323

Yes it never decrements at all.

    else return foo(x--)+x;

In the line where you call your function, you use a postdecrement, which means the value 10 is first passed to your next function and after that, it is decremented - which never happens since no function ever returns

Upvotes: 0

Related Questions