Для решения одной и той же задачи можно использовать и итерационные и рекурсивные алгоритмы. Однако программы, записанные различными способами, по своим свойствам заметно отличаются друг от друга. Поэтому нужно взвешивать, какой способ, в какой ситуации лучше. Факторами, влияющими на решение, могут быть эффективность вычислений в отношении времени или объема памяти, длина программы, ее прозрачность и понятность и т. д.
Каноническим примером рекурсивных функций является функция вычисления факториала числа. Число n! (n факториал) определяется как (n)*(n-1)*(n-2)* ... *(1). Факториал числа 0 равен 1. Заметьте также, что n! = (n)*(n-1)!.
Математическое определение факториала рекурсивно и его реализация через рекурсивную функцию совершенно естественна. Ниже приведена программная реализация функции вычисления факториала числа на языке Паскаль.
procedure Factorial(N:integer; var Y:integer);
Var
NewN, NewY : integer;
Begin
if N = 0 then Y := 1
Else
if N > 0 then
Begin
NewN := N – 1;
Factorial(NewN, NewY);
Y := NewY * N
End
end;
Как видно из приведенного листинга процедура вычисления факториала является рекурсивной, поскольку она сама вызывает себя. Ниже приведена программная реализация функции вычисления факториала числа на языке Пролог.
Основная идея рекурсивного определения заключается в том, что функцию можно с помощью рекурентных формул свести к некоторым начальным значениям, к ранее определенным функциям или к самой определяемой функции, но с более «простыми» аргументами. Вычисление такой функции заканчивается в тот момент, когда оно сводится к известным начальным значениям. Таким образом, факт (0!) = 1 не будет использоваться до тех пор, пока в ходе исполнения программы не будет порожден вызов, специально требующий вычисления значения 0!.
В противоположность этому программист, использующий какой-либо традиционный язык программирования, предпочел бы, вероятно, написать программу вычисления факториала, поведение которой было бы в точности обратным по отношению к обсуждавшемуся выше: каждое полученное значение факториала сразу бы использовалось для вычисления значения очередного, большего факториала. Т.е. вычисление производилось бы методом снизу вверх. Такой метод является итеративным, и он более эффективен, чем рекурсивный метод сверху вниз. Ниже приведена итерационная версия программы вычисления факториала числа на языке Паскаль.
procedure factorial(N:integer; var Y:integer);
Var
I, P : integer;
Begin
I:=0; P:=1;
while I < N do
Begin
I := I+1;
P := P*I
end;
Y:=P;
end;
Основное отличие рекурсии от итерации с точки зрения исполнения состоит в том, что рекурсия в общем случае требует объем памяти, линейно зависящий от числа выполняемых рекурсивных обращений, в то время как объем памяти, требуемый для выполнения итераций, ограничен константой, не зависящий от числа выполняемых итераций. Существует класс рекурсивных программ (в точности тех, которые могут быть преобразованы непосредственно в итерационные программы), выполняемых с использованием постоянного объема памяти. Метод реализации, приводящий к подобной экономии памяти, называется оптимизацией остатка рекурсии или, точнее, оптимизацией последнего обращения. Для выполнения оптимизации остатка рекурсии необходимо, чтобы соблюдались следующие условия:
1. Вызов рекурсивно-определенного предиката должен являться самой последней подцелью предложения.
2. Ранее в предложении не должно быть точек возврата.
Ниже приведена итерационная версия программы вычисления факториала числа на языке Пролог.
factorial(N, Y):-factorial(0, 1, N, Y).
factorial(N, Y, N, Y):-!.
factorial(I, P, N, Y):-I<N,
NewI=I+1, NewP=P*NewI,
factorial(NewI, NewP, N, Y).
?- factorial(3, Y)
Y=6
Эта программа порождает вычисления методом снизу вверх – значение 1! вычисляется исходя из значения 0!, затем значение 2! исходя из 1! и т. д. В Прологе отсутствуют «локальные» переменные для удержания промежуточных результатов и их изменения в процессе вычисления. Поэтому для реализации итерационных алгоритмов, требующих сохранения промежуточных результатов, процедуры Пролога дополняются аргументами, называемыми накопителями. Накопители являются логическими переменными, а не ячейками памяти. В процессе итерации передается не адрес, а значение. Так как логические переменные обладают свойством «одноразовой записи», то измененное значение – новая логическая переменная – передается каждый раз. Поэтому для указания измененных значений в обозначениях переменных используется префикс New. Обычно промежуточное значение соответствует результату вычисления при завершении итерации. Это значение сопоставляется результирующей переменной с помощью единичного предложения процедуры. В приведенном примере промежуточное значение факториала числа сохраняется в переменной P. Как только значение счетчика I будет равно значению N, результат вычисления факториала копируется из переменной P в переменную Y и возвращается пользователю. При выполнении целевого утверждения factorial(3, Y) получим следующую последовательность рекурсивных вызовов:
