0

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;
}
John DeBord
  • 638
  • 1
  • 5
  • 17
  • 5
    `val - 1` doesn't affect the variable `val`, but with `--val` you have a decrement on `val` – danilo Feb 14 '18 at 23:26
  • 1
    Get familiar with the concept of a "stack frame". – DeiDei Feb 14 '18 at 23:27
  • 1
    This is the type of problem that's pretty easy to check when you step through it in your debugger. – MrEricSir Feb 14 '18 at 23:28
  • 2
    Using a variable whose value is auto incremented/decremented in the same expression results in undefined behavior. – Ferruccio Feb 14 '18 at 23:30
  • 1
    @MrEricSir: Not really. The debugger doesn't tell you when your program has undefined behaviour. – Lightness Races in Orbit Feb 14 '18 at 23:46
  • @Lightness Yes the debugger won't flag UB. But since the UB in this case does behave consistently on OP's compiler. If OP had stepped through the code with a debugger, OP should see that `factorial(1)` is evaluated as `factorial(0) * 0` ... Which is the point MrEricSir was making. – Disillusioned Feb 15 '18 at 00:04
  • @CraigYoung: _"the UB in this case does behave consistently on OP's compiler"_ You do not know that until you have tested it on the OP's compiler infinite times. – Lightness Races in Orbit Feb 15 '18 at 00:05
  • @CraigYoung: _"Which is the point MrEricSir was making."_ Yes I understood the point, which was to foster an incorrect understanding both of this program and of the constructions at play here. – Lightness Races in Orbit Feb 15 '18 at 00:06
  • @Lightness I often see 2 extreme misinterpretations of UB, at opposite ends of the spectrum. 1) Too optimistic: "I observed x behaviour in a few simple cases, I can assume UB behaves as x" (_obviously not_) 2) Too pessimistic: "UB means the compiler might eat your cat" (_again, obviously not_). The point is, barring actual bugs in the compiler: the compiler may generate machine code that exhibits UB, but the compiler itself does not exhibit UB. Therefore given particular input the compiler will always output the _same binaries_. – Disillusioned Feb 15 '18 at 02:12
  • OP's compiler evidently decrements `val` ***before*** performing the multiplication given OP's source code. Obviously a change to _input_ (such as optimisation settings) may change the compiler's output. But the simple fact is that this ***most certainly is*** something OP could have debugged to observe ***why*** his program was behaving unexpectedly. (Though obviously that wouldn't help OP understand that his code would exhibit UB.) – Disillusioned Feb 15 '18 at 02:16
  • @CraigYoung: _"Therefore given particular input the compiler will always output the same binaries."_ That's an unfounded assumption, and it's not extreme to say so. The rest makes sense. – Lightness Races in Orbit Feb 15 '18 at 12:25

3 Answers3

6

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.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • I downvoted for the original answer,`They only seem identical if you don't read them - one says val - 1 and the other says --val`, as this was quite obvious that it was being asked about the functional difference between the two. With the edit, I have removed my downvote. –  Feb 14 '18 at 23:31
  • @Thebluefish: You must be on 56k, with the answer trickling through really slowly like loading a full-screen GIF in the 1990s... ;) – Lightness Races in Orbit Feb 14 '18 at 23:32
  • It would appear to be so ;) –  Feb 14 '18 at 23:33
  • 1
    To reaffirm - the radically different results come because the second program has undefined behaviour. Any further analysis is mathematically impossible. – Lightness Races in Orbit Feb 14 '18 at 23:36
  • 1
    Plus one for mentioning UB – Killzone Kid Feb 14 '18 at 23:36
  • 1
    _If_ this weren't UB, and _if_ the compiler chose to evaluate the decrement first then you end up with a string of multiplications ending in 0 (`var == 1`, `--var`, `return factorial(0) * 0`) which will then get passed up to the top level. In an alternate universe somewhere, that's why the OP observed the result 0. In this universe, though, it's just because the program has undefined behaviour. – Lightness Races in Orbit Feb 14 '18 at 23:49
  • You don't need to invoke UB to see what the difference is between `--var` and `var - 1`. – user253751 Feb 15 '18 at 00:41
  • @immibis: No, you don't, but the OP is invoking it regardless, in _this_ program that is being asked about. – Lightness Races in Orbit Feb 15 '18 at 00:43
4

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.

AaronHolland
  • 1,595
  • 1
  • 16
  • 32
1

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.

R Sahu
  • 204,454
  • 14
  • 159
  • 270
  • It is free to fry some fish then atomise it and spread the molecules in an uneven distribution about the Pleiades constellation. – Lightness Races in Orbit Feb 15 '18 at 00:06
  • @LightnessRacesinOrbit, among other things. – R Sahu Feb 15 '18 at 00:08
  • Indeed. Seriously, don't underestimate [the bizarre potential that UB has](https://stackoverflow.com/q/48731306/560648); there are _way_ more than two possible results here. – Lightness Races in Orbit Feb 15 '18 at 00:10
  • @LightnessRacesinOrbit, no kidding. The crap that optimizers can spring on you is something I am nowhere near familiar with. – R Sahu Feb 15 '18 at 00:13
  • @Lightness "_It is free to fry some fish then atomise it and spread the molecules in an uneven distribution about the Pleiades constellation._" Utter rubbish. Stop being alarmist. Incredulous claims just reduce credibility. Yes you're emphasising that you have absolutely no guarantees about what might or might not happen, but that's not going to make the compiler violate the laws of physics! This blinkered view seems to have made you lose sight of the ***fact*** that OP _could have_ debugged his program to observe what his compiler _actually **did do**_ with his code. – Disillusioned Feb 15 '18 at 02:22
  • @CraigYoung: It's not a "blinkered view", it is a robust and rigourous view that will lead to robust and rigourous code. Lern2abstract – Lightness Races in Orbit Feb 15 '18 at 12:29