Пример 51

Пример

Исходные данные:	N - целое неотрицательное число.
Результат:	факториал числа N

program FactorRec; {вычисление факториала с использованием рекурсии} var N: integer; function Factor(N: integer): integer; begin if N = 0 then Factor:= 1 else Factor:= N * Factor(N-1); end; begin {начало программы} writeln('введите целое число'); read(N); writeln('Факториал ', N:4, '=', Factor(N)); end.

С помощью выражения Factor(N-1) эта функция будет вызывать сама себя до тех пор, пока значение параметра не станет равным 0. При каждом повторном вызове функции создается новый экземпляр памяти для всех локальных переменных и для самой функции, который запоминается в стеке. Пусть N = 4, тогда в результате выполнения функции Factor будет создан стек, представленный на Рис.9. Этот процесс называется процессом развертывания рекурсии.

Рис. 9. Процесс развертывания рекурсии

Как только N становится равным 0, вычисляется первое значение факториала Factor = 1, которое затем подставляется в соответствующий экземпляр памяти. Теперь на каждом очередном шаге значения всех членов выражения N * Faсtor(N - 1) известны и алгоритм подставляет в это выражение значение, полученное на предыдущем шаге. Начинается процесс свертывания рекурсии, представленный на Рис.10, и вычисляется значение Factor = 24.

Рис. 10. Процесс свертывания рекурсии

Отметим, что вычисление выражения в процессе свертывания рекурсии осуществляется с запомненным значением N, поскольку N передается в функцию по значению (без параметра Var). Так, на 4-м шаге в выражение подставляется значение Factor (0)=1 и N = 1, на 3-м шаге - Factor (1) = 1 и N = 2 и т.д.
Для сравнения приведем программу в примере 51, где рекурсия заменяется обычной итерацией.

program FactorIt; {вычисление факториала с использованием итерации} var F, N, I: integer; begin writeln('Введите целое число '); read(N); F:= 1; for I:= 1 to N do F:= F * I; writeln('Факториал', N:4, '=', F); end.

Бесспорно, что реализация вычисления факториала в примере 51 является более традиционной, однако в этом случае используется три переменных.

Сформулируем свойства рекурсивных алгоритмов:

1. Наличие тривиального случая.
Правильный рекурсивный алгоритм не должен создавать бесконечную последовательность вызовов самого себя. Для этого он обязательно должен содержать нерекурсивный выход, т.е. при некоторых исходных данных вычисления в алгоритме должны производиться без вызовов его самого - тривиальный случай. Примером тривиального случая в рекурсивном алгоритме вычисления N! является условие N = 0.
2. Определение сложного случая в терминах более простого.
При любых исходных данных нерекурсивный выход должен достигаться за конечное число рекурсивных вызовов. Для этого каждый новый вызов рекурсивного алгоритма должен решать более простую задачу, т.е. рекурсивный алгоритм должен содержать определение некоторого сложного случая в терминах более простого случая. В случае вычисления факториала - это вычисление по формуле N! = N * (N-1)!, где N уменьшается при каждом рекурсивном вызове.

Когда нужна рекурсия? Выбор зависит от конкретной задачи. В общем случае рекурсия требует дополнительных расходов памяти, т.к. она реализуется с использованием стеков, однако, если задача или используемые данные определены рекурсивно, применение рекурсии часто дает более простое решение и реализация алгоритма выглядит изящнее.

Дата добавления: 2014-01-04