How the following recursion outputs 48?

Question

How the following recursion in C outputs 48 ? I expected the output to be 0.

#include<stdio.h>

int fun(int i) {
   if(i<2)
      return 1;
   else {
      return fun(--i) * i * fun(--i);
   }   
}

int main() {
   printf("%d",fun(5));
   return 0;
}

@Alex K. when i put i at the end in the last line of the recursion i.e {return fun(--i)* fun(--i) * i;} the output is 0. — Rajesh Sethi, Mar 24 '15 at 17:32
Writing too much code on one line will often cause problems because you get illegible code. I bet if you wrote this more clearly, the problems would be come more apparent. — Almo, Mar 24 '15 at 17:33
I already posted the duplicate link, but to sum up your problem: it's not specified which order `fun(--i)`, `i` , and `fun(--i)` are evaluated in. You don't know if `--i` is going to be evaluated before or after `i` is evaluated. — Cornstalks, Mar 24 '15 at 17:35
if i is evaluated after both the decrement operators then the result is 0 — Rajesh Sethi, Mar 24 '15 at 17:41
No, to me, this is happening for another reason. Marking it for reopening (I have an answer) — axelduch, Mar 24 '15 at 17:45
It still outputs 48 without the `--i` UB: http://coliru.stacked-crooked.com/a/7540075283c56c21 — tmlen, Mar 24 '15 at 17:46
I agree: modify the question to remove the UB. I'm voting to reopen because the duplicate I linked to is about C++, whereas this is a C question (dumb mistake on my part). — Cornstalks, Mar 24 '15 at 17:55
@RajeshSethi I reverted your edit as it will **not** execute the same things (because order matters here) as in the previous version — axelduch, Mar 24 '15 at 18:13
@aduch: The order of evaluation of `i`, `--i` and `--i` is undefined in that expression. The order that they are written in __doesn't matter__. — Bill Lynch, Mar 24 '15 at 18:31
This is still undefined behavior. It should be closed as a duplicate of http://stackoverflow.com/questions/949433/why-are-these-constructs-using-undefined-behavior — Bill Lynch, Mar 25 '15 at 14:30

score 2 · Answer 1 · edited May 23 '17 at 12:14

The expression fun(--i) * i * fun(--i) exhibits undefined behavior. So we can't make any assumptions about what that would produce. If you are curious why it is undefined, then please read: Why are these constructs (using ++) undefined behavior?

We can attempt to remove the undefined behavior, and talk about that though:

int fun(int i) {
   if(i<2)
      return 1;
   else {
      return fun(i - 1) * (i - 1) * fun(i - 2);
   }   
}

fun(5) should and does produce 48 with the corrected code. And if we need to prove that...

fun(0) == 1
fun(1) == 1
fun(2) == fun(1) * 1 * fun(0) == 1 * 1 * 1 == 1
fun(3) == fun(2) * 2 * fun(1) == 1 * 2 * 1 == 2
fun(4) == fun(3) * 3 * fun(2) == 2 * 3 * 1 == 6
fun(5) == fun(4) * 4 * fun(3) == 6 * 4 * 2 == 48

How the following recursion outputs 48?

1 Answers1