Рекурсивное программирование в логических языках является основным видом программирования. Эффективность рекурсивных программ повышается с помощью хвостовой рекурсии. В большинстве декларативных языков программирования имеется оптимизация хвостовой рекурсии.
Рассмотрим рекурсию на примере нахождения всем известного факториала.
implement main
open core, console
class predicates
fact:(integer, integer) procedure (i, o).
clauses
fact(0, 1) :- !.
fact(N, F) :- fact(N-1, X), F = N * X.
run():-
init(),
write("Введите число n = "),
N=read(),
fact(N, F),
write(N, "! = ", F),
_=readLine(), nl,
write("Конец. Нажмите Enter "),
_=readLine(),
nl.
end implement main
goal
mainExe::run(main::run).fact(3, R).
Данная цель не унифицируется с заголовком первого правила, но унифицируется с заголовком второго правила, которое имеет вид:
fact(N1, F1):- fact(N1 - 1, X1), F1 = N1 * X1.
Тогда
N1 = 3, F1 = R. Новая цель имеет вид: fact(2, X1), R = 3 * X1.
Сначала вызывается подцель:
fact(2, X1).
Она также не унифицируется с заголовком первого правила, но унифицируется с заголовком второго:
fact(N2, F2):- fact(N2 - 1, X2), F2 = N2 * X2.
При этом
N2 = 2, F2 = X1. Следующая цель имеет вид: fact(1, X2), X1 = 2 * X2, R = 3 * X1.
Вызывается подцель:
fact(1, X2).
Эта подцель также унифицируется с заголовком только второго правила:
fact(N3, F3):- fact(N3 - 1, X3), F3 = N3 * X3.
При этом
N3 = 1, F3 = X2. Следующая цель выглядит так: fact(0, X3), X2 = 1 * X3, X1 = 2 * X2, R = 3 * X1.
Вызывается первая подцель:
fact(0, X3).
Она унифицируется с заголовком первого правила:
fact(0, 1):- !.
При этом
X3 = 1. В теле этого правила стоит отсечение, поэтому других решений быть не может. Полученное значение передается в оставшуюся цель:X2 = 1 * X3, X1 = 2 * X2, R = 3 * X1.
Из первой подцели находится значение
X2 = 1. Оно передается в цель: X1 = 2 * X2, R = 3 * X1.
Из первой подцели следует, что
X1 = 2. Это значение передается в цель: R = 3 * X1.
Таким образом, получено решение:
R = 6.
Данная рекурсия является нисходящей. Нисходящая рекурсия последовательно разбивает задачу на все более простые, пока не доходит до граничной ситуации, в которой уже не требуется продолжения рекурсии.
В целях повышения эффективности вычислений перейдем к хвостовой рекурсии. Рекурсия – хвостовая, если вызов предиката самого себя идет последним в правиле, при этом до него нет недетерминированных вызовов. Хвостовая рекурсия соответствует итерации в процедурных языках программирования.
Рассмотрим другое определение факториала. В нем используются счетчик C и накопитель для хранения произведения первых C натуральных чисел:
implement main
open core, console
class predicates
fact:(integer, integer) procedure (i, o).
fact1: (integer, integer, integer, integer) procedure (i, i, i, o).
clauses
fact(N, F):- fact1(N, 0, 1, F).
fact1(N, N, F, F):- !.
fact1(N, C, X, F):- fact1(N, C + 1, (C + 1) * X, F).
run():-
init(),
write("Введите число n = "),
N=read(),
fact(N, F),
write(N, "! = ", F),
_=readLine(), nl,
write("Конец. Нажмите Enter "),
_=readLine(),
nl.
end implement main
goal
mainExe::run(main::run).fact(3, R).
Эта цель унифицируется с заголовком правила:
fact(N1, F1):- fact1(N1, 0, 1, F1).
При этом
N1 = 3, F1 = R. Далее вызывается цель: fact1(3, 0, 1, R).
Эта цель унифицируется только с заголовком последнего правила:
fact1(N2, C2, X2, F2):- fact1(N2, C2 + 1, (C2 + 1) * X2, F2).
При этом
N2 = 3, C2 = 0, X2 = 1, F2 = R. Теперь вызывается цель: fact1(3, 1, 1, R).
Она также унифицируется только с заголовком последнего правила:
fact1(N3, C3, X3, F3):- fact1(N3, C3 + 1, (C3 + 1) * X3, F3).
При этом
N3 = 3, C3 = 1, X3 = 1, F3 = R. Вызывается цель: fact1(3, 2, 2, R).
Она унифицируется с тем же правилом:
fact1(N4, C4, X4, F4):- fact1(N4, C4 + 1, (C4 + 1) * X4, F4).
Теперь
N4 = 3, C4 = 2, X4 = 2, F4 = R. Новая цель имеет вид: fact1(3, 3, 6, R).
Эта цель унифицируется с заголовком правила:
fact1(N5, N5, F5, F5):- !.
При этом
N5 = 3, F5 = 6, R = 6. Отсечение предотвращает поиск других решений. Итак, имеем: R = 6.
Это был пример восходящей рекурсии. В восходящей рекурсии промежуточные результаты вычисляются на каждом шаге рекурсии, так что ответ строится постепенно и передается в виде параметра рабочей памяти до тех пор, пока не будет достигнута конечная ситуация. К этому моменту ответ уже будет вычислен.
