CODEWITHSUNDEEP
c++recursion
John DeBord
John DeBord

Reputation: 705

Need a fresh perspective on recursion

I just can't wrap my head around this.
Why do these two functions produce radically different results,
when line 4 seems identical?

Version I

int factorial(int val) // input=5; output=120
{
    if (val != 0)
        return factorial(val - 1) * val;
    return 1;
}

Version II

int factorial(int val) // input=5; output=0
{
    if (val != 0)
        return factorial(--val) * val;
    return 1;
}

Upvotes: 0

Views: 82

Answers (3)

R Sahu
R Sahu

Reputation: 206717

Use of 

return factorial(--val) * val;

is cause for undefined behavior. Don't use it.

For evaluating the expression, the compiler is free to evaluate factorial(--val) first, then evaluate val, and then perform the multiplication. It is also free to evaluate val first, then evaluate factorial(--val), and then perform the multiplication.

If the compiler chooses the first strategy, that statement is equivalent to:

--val;
return factorial(val)*val;

As you can see, that is incorrect.

If the compiler chooses the second strategy, that statement is equivalent to:

int res = factorial(val-1)*val;
--val
return res;

Had the compiler followed this strategy, you'd have gotten the correct answer.

OTOH, the statment

return factorial(val-1)*val;

does not suffer from that problem and always returns the correct value.

Upvotes: 1

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385325

They only seem identical if you don't read them - one says val - 1 and the other says --val.

  • val - 1: Subtraction. Evaluates to the value of val, minus one
  • --val: Decrement. Reduces val by one, and evaluates to the new value

The latter example has undefined behaviour because you try to read val again on the same line.

Upvotes: 6

AaronHolland
AaronHolland

Reputation: 1685

Version 2 changes the value of val via the --val, where version 1 only subtracts 1 from val but doesn't update the value of val when doing so.

Upvotes: 4

Related Questions