Рекурсивная функция PHP (факториал числа)

127

17 февраля 2021, 20:00

Объясните, пожалуйста, как работает рекурсивная функция на примере вычисления факториала из числа 4.

Вычисление, которое происходит в данной функции: 4 * 3 * 2 * 1 = 24.

Вот пример кода:

<?php
function fact($n) {
    if ($n <= 0) return 1;
    return $n * fact ($n-1);
}
echo fact(4);
?>

Насколько я понял, алгоритм выполнения функции выглядит следующим образом:

Answer 1

return 4 * fact (4-1); // делаем вычисление: 4 * (4-1) = 12

Здесь не так - второй аргумент же будет возвращён функцией, которая ещё не отработала

 делается вычисление 4 * fact(3)  //уровень 1, запомнили множитель 4
 делается вычисление 3 * fact(2)  //уровень 2, запомнили множитель 3
 делается вычисление 2 * fact(1)  //уровень 3, запомнили множитель 2 
 делается вычисление 1 * fact(0)  //уровень 4, запомнили множитель 1
 - всё, дошли до остановки рекурсии, возвращаем 1    //уровень 5
 1 * 1    //вернулись на уровень 4, используем запомненный множитель 1
 2 * 1    //вернулись на уровень 3
 3 * 2    //вернулись на уровень 2
 4 * 6    //вернулись на уровень 1
  на верхний уровень отдаётся результат 24

Представьте, что в комнате с двумя окошками сидит математик.
В левое окошко ему подают бумажку с числом.
Если число 0, он пишет 1, и возвращает в левое окно.
Иначе на новой бумажке пишет число, на единицу меньшее, и передаёт в правое окно.
Если ему передают бумажку из правого окна, он перемножает числа, и результат передаёт налево.

И вот таких комнат бесконечный ряд - тогда математики могут вычислить факториал любого числа.

Теперь пусть у нас всего одна комната, а переносить бумажки снаружи из правого окна в левое и из левого в правое будет оператор.
А математик складывает бумажки из левого в стопку, а когда приходит из правого - берет верхнюю из стопки, и перемножает с числом на ней.
Когда у него кончаются бумажки в стопке - он сообщает об этом оператору - работа завершена.