Шаг 172.
Рекурсия на Python. Вложенная рекурсия и снова хвостовая. Итерационный подход к хвостовой рекурсии. Факториал

    На этом шаге мы рассмотрим особенности вычисления факториала.

    Рассмотрим итерационную версию функции вычисления факториала из примера 11.3. Метод вычисляет искомое значение, последовательно повторяя одни и те же действия в цикле while. В этом алгоритме начальный параметр n задаёт количество итераций цикла, тогда как переменную p можно считать накопителем промежуточных результатов, которая по завершении цикла будет содержать искомый факториал.


Пример 11.3. Итерационная функция вычисления факториала
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).

Таблица 1. Состояния программы при вычислении факториала 4! итерационной функцией
        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 приведена возможная реализация хвостовой рекурсии, где функция-оболочка вызывает рекурсивный метод со вторым аргументом, равным единице.


Пример 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. Сходство между итерационным и хвостовым рекурсивным кодами, вычисляющими факториал

    На следующем шаге мы рассмотрим приведение десятичного числа к другому основанию.




Предыдущий шаг Содержание Следующий шаг