Recursion in C with Pre increment

Question

int fact_rec(int n)
{
    printf("%d\n",n);
    if(n==1) return n;
    else return fact_rec(--n)*n;
    //else return n*fact_rec(--n); gives same result
    //correct output comes for n*fact(n-1)
}

In the above recursive implementation of the factorial function, fact_rec(5) returns 24. Whereas, if I use n*fact_rec(n-1) in place of n*fact_rec(--n) the output is correct : 120. Also, it doesn't matter whether I use n*fact_rec(--n) or fact_rec(--n)*n. Shouldn't it matter if I use n*fact_rec(--n) or fact_rec(--n)*n?

And shouldn't the output have been 120 in all the cases?

Answer 1

--n in your function really means:

int fact_rec(int n) {
    printf("%d\n",n);

    if(n==1) {
         return n; 
    } else {
        n = n - 1; /* <---- effect of --n */
        return fact_rec(n)*n;
    }
}

Answer 2

The problem is here:

else return fact_rec(--n)*n;

you're decrementing n before the multipliation

so if n starts as 5 it runs as

return fact_rec(4)*4;

Edit: Down voted for a correct answer to the question? I don't get it.

Answer 3

Your confusion seems to be about the order - unlike the other answers, I am assuming you already know what --n does...

The compiler knows it needs the value of fact_rec(--n) before it can evaluate fact_rec(--n)*n whichever way round you write it, so the function is evaluated first, and the value of n multipled has always already been decremented.

Answer 4

return fact_rec(--n)*n

is dangerous. The order of argument evaluation is undefined in C (except for &&, ||, comma and ternary operators) so value for second occurrence of n could vary.

The rule of thumb: never use variable you are incrementing/decrementing twice in one expression.

Answer 5

There is actually no need to modify n at all. return n * fact_rec(n - 1) takes care of it and is the right way to do it.