El Mestre - 1 year ago 60
Java Question

# Understanding Java behaviour in recursive factorial

I created two recursive methods to calculate factorial as follows:

``````private int fact1(int n) {
if (n == 0 || n == 1)
return 1;
return n * fact1(--n);

}

private int fact2(int n) {
if (n == 0 || n == 1)
return 1;
return fact2(--n) * n;
}
``````

When I call
`fact1(4)`
it returns
`24`
. When I call
`fact2(4)`
it returns
`6`
(EDIT: is not returning
`18`
but
`6`
). I know the second method is making 3 * 2 * 1, but I don't understand why not 4 * 3 * 2 * 1.

``````//fact3(4) returns 60.
return (n + 1) * fact3(--n); // wrong
//fact4(4) returns 24
return fact4(--n) * (n + 1); // works
``````

Why is the method exhibiting this behavior??

The question is about the different behaviour. I know
`n * fact(n-1)`
is the better way to solve it.

Can someone help me to understand the evaluation of this expression? Thanks!

It all comes down to the difference between these expressions:

``````return n * f(--n);

return f(--n) * n;
``````

When `n = 4`, these expressions are evaluated like this:

``````return 4 * f(3);

return f(3) * 3;
``````

Because the moment `--n` is evaluated, the value of `n` is decreased by 1. This is how the prefix `--` operator works.

It might help to recursively evaluate the entire expressions by hand. The first one:

``````// first
return 4 * f(3);
return 4 * 3 * f(2);
return 4 * 3 * 2 * f(1);
return 4 * 3 * 2 * 1;

// second
return f(3) * 3;
return f(2) * 2 * 3;
return f(1) * 1 * 2 * 3;
return 1 * 1 * 2 * 3;
``````

On a related note, guess how this will be evaluated:

``````return f(n--) * n;
``````

It will be:

``````return f(4) * 3;
``````

Because here the postfix `--` operator is used: the -1 decrement will be applied after the evaluation of `n` in `f(...)`.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download