El Mestre - 1 year ago 45

Java Question

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)`

`24`

`fact2(4)`

`6`

`18`

`6`

The same happens if I change the return to

`//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)`

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

Answer Source

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(...)`

.