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

Рассмотрим итерационную версию функции вычисления факториала из примера 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

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

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

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