На этом шаге мы рассмотрим особенности вычисления факториала.
Рассмотрим итерационную версию функции вычисления факториала из примера 11.3. Метод вычисляет искомое значение, последовательно повторяя одни и те же действия в цикле while. В этом алгоритме начальный параметр n задаёт количество итераций цикла, тогда как переменную p можно считать накопителем промежуточных результатов, которая по завершении цикла будет содержать искомый факториал.
1 2 3 4 5 6 7 |
def factorial_iterative(n): p = 1 while n > 0: p = p * n n = n - 1 return p |
В таблице 1 приведены значения переменных и параметров метода или состояние памяти программы для каждой итерации цикла при вычислении 4! (иными словами, каждый вход таблицы отображает значения n и p при проверке программой условия в строке 3).
n | p |
---|---|
4 | 1 |
3 | 4 |
2 | 12 |
1 | 24 |
0 | 24 |
Для вычисления факториала можно написать равнозначную хвостовую рекурсивную функцию, которая выполняет те же действия, что итерационный алгоритм. А именно: метод (скажем, f) требует обоих параметров n и p и должен вызывать функцию со значениями параметров из таблицы 1. Другими словами, хвостовой рекурсивный метод должен генерировать следующие рекурсивные вызовы:
f(4, 1) → f(3, 4) → f(2, 12) → f(1, 24) → f(0, 24) = 24.
Фактически они задают соответствие между рекурсивным хвостовым вызовом и шагом итерационного алгоритма. В частности, очевидно рекурсивное правило f(n, p) = f(n - 1, p * n), выполняющее, в сущности, все те действия по обновлению переменных, которые производятся в теле цикла итерационной версии. Отметим, что n задаёт количество вызовов функции, а p хранит промежуточные результаты, включая окончательный. Последний вызов соответствует начальному условию (при n = 0), когда метод возвращает свой второй параметр. Наконец, факториал n вычисляется при вызове f(n, 1), где параметры n и p достигают начальных (до входа в цикл) значений одноимённых переменных итерационной версии. В примере 11.4 приведена возможная реализация хвостовой рекурсии, где функция-оболочка вызывает рекурсивный метод со вторым аргументом, равным единице.
1 2 3 4 5 6 7 8 9 |
def factorial_tail(n, p): if n == 0: return p else: return factorial_tail(n - 1, p * n) def factorial_tail_recursive_wrapper(n): return factorial_tail(n, 1) |
Итерационные и хвостовые рекурсивные функции очень похожи. Рисунок 1 показывает сходство обоих методов (рекурсивное условие проверяется до начального, чтобы использовать условие n > 0 в рекурсивном методе).
Рис.1. Сходство между итерационным и хвостовым рекурсивным кодами, вычисляющими факториал
На следующем шаге мы рассмотрим приведение десятичного числа к другому основанию.