Понимание поведения Java в рекурсивном факториала

Question

Я создал два рекурсивных методов для расчета факториала следующим образом:

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; 
} 

Когда я звоню fact1(4) возвращает 24. Когда я звоню fact2(4), он возвращает 6 (EDIT: не возвращается 18, но 6). Я знаю, что второй метод делает 3 * 2 * 1, но я не понимаю, почему не 4 * 3 * 2 * 1.

То же самое происходит, если я меняю возвращение к

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

Почему это метод, демонстрирующий такое поведение?

Вопрос о поведении. Я знаю, что n * fact(n-1) - лучший способ решить эту проблему.

Может кто-нибудь помочь мне понять оценку этого выражения? Благодаря!

Answer 1

Это все сводится к разнице между этими выражениями:

return n * f(--n); 

return f(--n) * n; 

Когда n = 4 эти выражения оцениваются как это:

return 4 * f(3); 

return f(3) * 3; 

Поскольку момент --n вычисляется, значение n уменьшается на 1. Вот как работает префикс --.

Это может помочь рекурсивно оценить все выражения вручную. Первый из них:

// 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; 

На соответствующую записку, догадаться, как это будет оцениваться:

return f(n--) * n; 

Это будет:

return f(4) * 3; 

Потому что здесь используется оператор постфикса --: -1-й декремент будет применен после оценки n в f(...).