Рекурсивная процедура — это процедура, которая вызывает сама себя. Рассмотрим пример вычисления факториала числа N:
Если N равно 1, то факториал равен 1. Иначе найти факториал N-1 и умножить его на N.
Таким образом, чтобы найти факториал 3, необходимо найти факториал 2, а чтобы найти факториал 2, необходимо вычислить факториал 1. Можно найти факториал 1 без обращения к другим факториалам, поэтому повторения не начнуться. Если есть факториал 1, то он умножается на 2, чтобы получить факториал 2, а затем, он умножается на 3, чтобы получить факториал 3.
В Турбо Прологе это выглядит так:
/* Файл Lab3_3.PRО Рекурсивная программа вычисления факториалов..(Рекурсивныйалгоритм)*/
predicates
factorial(inteqer, real)
clauses
factorial(1, 1):- !.
factorial(X, FactX):-
Y = X-1,
factorial (Y, FactY),
FactX = X*FactY.
Рассмотрим пример реализации вычисления факториала но с помощью итеративного алгоритма, когда аргументы используются в качестве переменных цикла.
/* Файл Lab3_4.PRО Рекурсивная программа вычисления факториалов. (Итеративный алгоритм)*/
predicates
factorial(integer, real)
factorial(integer, real, integer, real) /* Если числа превосходят 32767 — они объявляются вещественными */
clauses
factorial(N, FactN):-
factorial(N, FactN, 1, 1). %Задание начальных условий
factorial(N, FactN, N, FactN):- !.
factorial(N, FactN, I, P):-
NewI = I+1,
NewP = P*NewI,
factorial(N, FactN, NewI, NewP).
Промежуточная информация хранится в области памяти называемой «стек», которая создается каждый раз при вызове правила. Когда выполнение правила завершается, занятая его стеком память возвращается общему объему памяти, и выполнение продолжается со стеком, который использовался перед вызовом.
Преимущества рекурсии:
— Она может выражать алгоритмы, которые нельзя удобно выразить никаким другим образом.
— Она логически проще метода итерации.
— Она широко используется в обработке списков.
Рекурсия — хороший способ для описания задач, содержащих в себе подзадачу такого же типа.
Но у рекурсии есть один большой недостаток — она съедает память. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы она (вызывающая процедура) могла, после выполнения вызванной процедуры, возобновить выполнение на том же месте, где остановилась.
Этого можно избежать, когда процедура может вызвать себя без сохранения информации о своем состоянии, если вызывающая процедура не собирается возобновлять работу после выполнения вызванной процедуры.
Процедура вызывается последний раз, т.е. когда вызванная процедура завершит работу, вызывающая процедура не должна больше ничего делать. Значит, вызывающей процедуре не нужно сохранять свое состояние, потому что эта информация уже не понадобится. Как только вызванная процедура завершится, работа процессора должна идти в направлении, указанном для вызывающей процедуры после ее выполнения.
Например, процедура А вызывает процедуру В, а В вызывает С в качестве своего последнего шага. Когда В вызывает С, В не должно больше ничего делать. Поэтому, вместо того, чтобы сохранить для С текущее состояние о процедуре В, вы можете переместить информацию из стека В (который больше не нужен) в текущий стек С. Когда С закончит выполнение, она будет считаться вызванной непосредственно процедурой А.
А сейчас предположим, что на последнем шаге выполнения процедура В, вместо процедуры С вызывает себя. Рецепт говорит, что когда В вызывает В, стек для вызывающей В должен быть заменен стеком для вызванной В. Эта операция заключается в присвоении аргументам новых значений и возвратом процессора к началу процедуры. Поэтому, для процедуры это означает лишь обновление управляющих переменных в цикле.
Эта операция называется оптимизацией хвостовой рекурсии или оптимизацией последнего вызова.
Чтобы задать хвостовую рекурсию необходимо, чтобы:
1. Вызов являлся самой последней подцелью предложения.
2. Ранее в предложении не было возвратных точек.
Пример:
count(N):- % хвостовая рекурсия, которая не истощает память.
write(N), nl,
NewN = N+1,
count(NewN).
Цель count(0) будет печатать целые числа начиная с 0 и никогда не остановится. В конечном счете, ошибки округления приведут к печати неточных чисел, но остановки не произойдет.
Ошибочные способы хвостовой рекурсии:
1. Если рекурсивный вызов не самый последний шаг, процедура не является хвостовой рекурсией:
badcount1(X):-
write(X), nl,
NewX = X+1,
badcount1(NewX),
nl.
2. Другой способ остановить хвостовую рекурсию — оставить альтернативу непроверенной во время выполнения рекурсивного вызова. Тогда стек должен быть сохранен как в случае неудачного завершения рекурсивного вызова. Вызывающая процедура может вернуться и искать альтернативу. Например:
badcount2(X):-
write(X), nl,
NewX = X+1,
badcount2(NewX).
badcount2(X):-
X < 0,
write(«X is negative.»).
3. Для остановки хвостовой рекурсии не обязательно иметь рекурсивную процедуру отдельным предложением. Непроверенная альтернатива может также быть и в других вызываемых предложениях. Например:
badcount3(X):-
write(X), nl,
NewX = X+1,
check(NewX),
badcount3(NewX).
check(Z):- Z >= 0.
check(Z):- Z < 0.
Предположим, что Х положительная, как это обычно бывает. Тогда, когда badcount3 вызывает себя, первое предложение check достигает цели, а второе предложение check еще не выполнено. Поэтому, badcount3 сохраняет свой стек неизменным, чтобы вернуться и выполнить второе предложение check, как будто рекурсивный вызов завершился неудачно.
