При этом не происходит копирования кода выполнения, но все аргументы и промежуточные переменные копируются в стек, который создается каждый раз при вызове рекурсивного правила.
Когда выполнение правила завершается, занятая стеком память освобождается и выполнение продолжается в стеке правила-родителя.
Пример 48: написать программу вычисления факториала.
Для вычисления факториала используется последовательное вычисление произведения ряда чисел. Его значение образуется после извлечения значений соответствующих переменных из стека, используемых как список параметров для последнего предиката в теле правила. Этот последний предикат вызывается после завершения рекурсии.
Пример 49: написать программу, генерирующую числа Фибоначчи до заданного значения.
predicates
f (byte, word)
clauses
f (1, 1).
f (2, 1).
f(N, F):- N1=N-1, f (N1, F1), N2=N1-1, f (N2,F2), F=F1+F2.
goal
f (10, Fib).
У рекурсии есть три основных преимущества:
· логическая простота по сравнению с итерацией;
· широкое применение при обработке списков;
· возможность моделирования алгоритмов, которые нельзя эффективно выразить никаким другим способом (например, описания задач, содержащих в себе подзадачи такого же типа).
У рекурсии есть один большой недостаток – использование большого объема памяти. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы вызывающая процедура могла, после завершения вызванной процедуры, возобновить выполнение на том месте, где остановилась.
Рассмотрим специальный случай, когда процедура может вызвать себя без сохранения информации о своем состоянии.
Предположим, что процедура вызывается последний раз, то есть после вызванной копии, вызывающая процедура не возобновит свою работу, то есть при этом стек вызывающей процедуры должен быть заменен стеком вызванной копии. При этом аргументам процедуры просто присваиваются новые значения и выполнение возвращается на начало вызывающей процедуры. С процедурной точки зрения этот процесс напоминает обновление управляющих переменных в цикле.
Создание хвостовой рекурсии в программе на Прологе означает, что:
· вызов рекурсивной процедуры является самой последней посылкой в правой части правила;
· до вызова рекурсивной процедуры в правой части правила не было точек отката.
Приведем примеры хвостовой рекурсии.
Пример 50:рекурсивный счетчик с оптимизированной хвостовой рекурсией.
count(100).
count(N):-write(N),nl,N1=N+1,count(N1).
goal
nl, count(0).
Модифицируем этот пример так, чтобы хвостовой рекурсии не стало.
Пример 51:рекурсивный счетчик без хвостовой рекурсии.
count1(100).
count1(N):-write(N),N1=N+1,count1(N1),nl.
goal
nl, count1(0).
Из-за вызова предиката nl после вызова рекурсивного предиката должен сохраняться стек.
Пример 52:рекурсивный счетчик без хвостовой рекурсии.
count2(100).
count2(N):-write(N),nl,N1=N+1,count2(N1).
count2(N):-N<0, write(“N – отрицательное число“).
goal
nl, count2(0).
Здесь есть непроверенная альтернатива до вызова рекурсивного предиката (третье правило), которое должно проверяться, если второе правило завершится неудачно. Таким образом стек должен быть сохранен.
Пример 53:рекурсивный счетчик без хвостовой рекурсии.
Здесь тоже есть непроверенная альтернатива до вызова рекурсивного предиката (предикат check). Случаи в примерах 52 и 53 хуже, чем в примере 51, так как они генерируют точки возврата.
Очень просто сделать рекурсивный вызов последним в правой части правила, но как избежать альтернатив? Для этого следует использовать предикат отсечения, который предотвращает возвраты в точки, левее предиката отсечения. Модифицируем 52 и 53 примеры так, чтобы была хвостовая рекурсия.
Пример 54:рекурсивный счетчик из примера 52 с хвостовой рекурсией.
count4(100).
count4(N):-N>0,!,write(N),N1=N+1,count4(N1).
count4(N):- write(“N – отрицательное число“).
goal
nl, count4(0).
Пример 55:рекурсивный счетчик из примера 53 с хвостовой рекурсией.
