Рекурсивное программирование в логических языках является основным видом программирования. Эффективность рекурсивных программ повышается с помощью хвостовой рекурсии. В большинстве декларативных языков программирования имеется оптимизация хвостовой рекурсии.

Рассмотрим рекурсию на примере нахождения всем известного факториала.

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.

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

                                                                       << предыдущий | следующий >>


2016-06-05 • Просмотров [ 252 ]