/* Программа 8 */

domains

n, f = integer

predicates

factorial(n, f)

clauses

factorial(1,1).

factorial(N, ResN) :-

N>1,

N1=N-1,

factorial(N1,FactN1),

ResN = N*FactN1.

Предложение factorial(1,1) утверждает, что 1!=1. Рекурсивное правило factorial(N,ResN) содержит условие выхода, определяемое неравенством N>1. До тех пор пока это условие выполняется, рекурсивное правило будет работать. Условием завершения рекурсии является неуспех (нарушение выполнения) неравенства N>1.

Программа 8 не содержит раздела goal и поэтому рассмотрим её функционирование на примере следующего внешнего запроса:

Goal: factorial(4AnsN)

Сначала программа пытается сопоставить цель с фактом factorial(1, 1). Сопоставление терпит неудачу и поэтому программа переходит к сопоставлению цели с правилом factorial(N, ResN). Унификация успешна, переменная N получает значение 4, а переменная AnsN сцепляется с переменной ResN. Для данного частного случая рекурсивное правило условно можно представить следующим образом:

factorial(4, Ans4) :-

4>1,

N1=4-1,

factorial(3,Fact3),

Asn4 = 4*Fact3.

Условие N>1 в данном случае выполняется (4>1), поэтому переменная N1 получает значение 3(N1=4-1) и далее вызывает само себя, однако уже с новыми значениями параметров цели, а именно factorial(3, Fact3). При этом копии переменных N1 и FactN1 помещаются в стек.

Рекурсивный вызов правила опять возвращает программу к унификации новой цели factorial(3, Fact3) с предикатом factorial(1, 1). из раздела clauses. Унификация успеха не имеет и программа переходит к выполнению рекурсивного правила. Переменная N - получает значение 3, а переменная Fact3 сцепляется с переменной ResN. Тогда новое частное правило будет условно представляться следующим образом:

factorial(3, Ans3) :-

3>1,

N1=3-1,

factorial(2,Fact2),

Asn3 = 3*Fact2.

Процедура повторяется ещё раз при N=2:

factorial(2, Ans2) :-

2>1,

N1=2-1,

factorial(1,Fact1),

Asn1 = 2*Fact1.

Теперь при рекурсивном вызове правила новая цель factorial(1, Fact1) успешно унифицируется с предикатом factorial(1, 1), и переменная Fact1 связывается со значением единица (Fact1=1). Далее осуществляется переход к выполнению рекурсивного правила при N=1, а ResN=Fact1. Однако условие выхода из него не выполняется (1>1) и его выполнение, наконец, завершается вычислением результата с использованием данных стека, которые выбираются по принципу "последним пришёл - первым вышел", т.е.:

Fact2 = 2 * Fact1 = 2 * 1

Fact3 = 3 * Fact1 = 3 * 2 * 1

Ans4 = 4 * Fact1 = 4 * 3 * 2 * 1

Цель программы, таким образом, достигнута и система выдаёт ответ:

Ans4 = 24

1 Solution

В рассмотренной программе условие выхода из рекурсии определяется как подцель самого рекурсивного правила. Однако возможен и другой способ организации выхода из рекурсии - с использованием отсечения. Рассмотрим это на примере той же программы вычисления факториала; представленной в несколько модифицированном виде:

/* Программа 9 */

predicates

factorial(integer, integer)

clauses

factorial(1,1) :- !

factorial(X, FactX) :-

Y=X-1,

factorial(Y,FactY),

FactX = X * FactY.

Здесь условием выхода из рекурсии является предикат отсечения (!), используемый в правиле factorial(1,1) и рекурсия завершится(будет прервана).Как можно видеть в данном случае нет необходимости включать условие выхода в тело самого рекурсивного правила.