Программирование рекурсивных правил

Рекурсия является мощным методом программирования, в котором от­но­ше­ния между объектами можно определить, только пользуясь самими опре­де­ляемыми соотношениями. В Prolog рекурсия приобретает особую важность, так как здесь отсутствуют циклические конструкции. Правила, определяемые этим методом, называются рекурсивными.

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

Определим рекурсивно сумму чисел от 0 до N.

Для того чтобы вычислить сумму чисел от 0 до 10, необходимо поставить цель

goal sum(10, F),!.

F=55

Отсечение необходимо поставить, так как  в результате бэктрекинга система будет искать дополнительные решения и исчерпает память.

Можно программу видоизменить, чтобы не ставить отсечение в цели.

predicates

sum(integer, integer)

clauses

sum(0,0) if !.

sum(N,S) if N1=N-1,

sum(N1,S1),

S=S1+N.

goal sum(10, F).

F=55

1 Solution

Рассмотрим программирование рекурсивных правил на нечисловом примере.

domains

name=symbol

predicates

родитель(name,name)

clauses

родитель(pam,bob).

родитель(tom,bob).

…

родитель(pam,jim).

Определим отношение предок.

Для всех X и Z,

X —  предок Z, если   существует Y, такой, что

(1)    X — родитель Y и

(2)    Y — предок Z.

predicates

predok(name,name)

clauses

predok(X, Z) if родитель(X, Z).

predok(X, Z) if родитель(X, Y) and predok(Y, Z).

Можно задать системе вопрос: «Кто потомки Пам?» То есть: «Кто тот человек, чьим предком является Пам?»

goal predok(pam, Z).

Z=bob

Z=jim

Z=ann

Z=pat

4 Solutions

Решим еще несколько примеров.

Пример 1. Наибольший общий делитель.

Если заданы два целых числа X и Y, то их наибольший общий делитель D можно найти, руководствуясь следующими правилами:

• Если X и Y равны, то D равен X.
• Если X<Y, то D равен наибольшему общему делителю X разности X–Y.
• Если Y<X, то формулировка аналогична правилу (2), если X и Y поменять в нем местами.

predicates

nod(integer, integer, integer)

clauses

nod(X,X,X) if !.

nod(X,Y,D) if X<Y,

Y1=Y-X,

nod(X,Y1,D).

nod(X,Y,D) if Y<X,

nod(Y,X,D).

Пример 2. Нахождение пути между городами.

domains

town = symbol

distance = integer

predicates

road(town, town, distance)

route(town, town, distance)

clauses

road(tampa, houston, 200).

road(gordon, tampa, 300).

road(houston, gordon, 100).

road(houston, kansas_city, 120).

road(gordon, kansas_city, 130).

route(Town1, Town2, Distance) :- % (1)

road(Town1, Town2, Distance).

route(Town1, Town2, Distance) :- % (2)

road(Town1, X, Dist1),

route(X, Town2, Dist2),

Distance=Dist1+Dist2, !.

goal route(tampa, kansas_city, Dist).

Dist=320

1 Solution

Правило (2) является рекурсивным. При каждом обращении к этому пра­ви­лу должно выполняться перемещение на один город ближе к месту назна­че­ния. Отношение, описанное в заголовке правила (2), зависит от более простой версии самого себя, поскольку в правило (2) входит рекурсивная подцель. Пра­ви­ло (1) определяет условие окончания процесса рекурсии, то есть исходный вид процедуры. Если правило (1) станет истиной при выполнении запроса, то про­цесс рекурсии прекращается.

Пример 3. Генерация чисел.

Определим процедуру for (N1, N2, X), которая на бэктрекинге с помощью перебора порождает все целые числа, отвечающие условию
N1 <= X <= N2.

predicates

for(integer, integer, integer)

clauses

for (N1,N2,N1) if N1<=N2.

for (N1,N2,X)  if N1<N2,

N=N1+1,

for (N,N2,X).

goal for(1,4,K), S=K*2, write(K), write(" ", S), nl, fail.

1 2

2 4

3 6

4 8

No Solution

Пример 4. Опишем предикат, генерирующий бесконечное число циклов повторений поиска с возвратом.

predicates

repeat

clauses

repeat.

repeat if repeat.

Использовать repeat можно таким образом:

goal   repeat,

write(" возведение в квадрат числа ="),

readreal(X),

Y=X*X,

write(X," в степени 2 =",Y),nl,

write("продолжать да/нет(y/n)"),

readln(L),

L="n".

Контрольные вопросы и задания

1.     Дайте определение рекурсии.

2.     Приведите примеры художественной, литературной  рекурсии.

3.     Что является более общим понятием рекурсия или цикл?

4.     Дайте определение косвенной рекурсии.

5.     Дана программа

domains
name, a=string
predicates
a(name, a)
b(a, a)
sow(name, name)
clauses
a("Лена", nast).
a("Катя" ,sam).
a("Вика" ,slug).
b(sam,nast).
b(slug,sam).
sow(X,Y):-a(X,Z), a(Y,C),
b(C,Z).
sow(X,K):-a(X,Z),
a(Y,C),
b(C,Z),
sow(Y,K).
goal sow("Лена",K).
Какие ответы выдаст система?

6.     Дана база данных, содержащая факты

путешествия(Компания,Отправление,Прибытие,Вид транспорта). Определить рекурсивную процедуру можно_путешествовать из города А в город В.

7.     Опишите иерархическую феодальную лестницу от короля до рыцаря. Напишите процедуру, определяющую, кто встанет под знамена короля в ответ на его призыв собраться.

8.     В каких случаях следует применять конструкцию «повтор … отказ»?

9.     Разработайте алгоритм перевода алгоритмической конструкции «цикл пока» в рекурсивное правило.

10.           Разработайте алгоритм перевода алгоритмической конструкции «цикл до» в рекурсивное правило.

11.           Разработайте алгоритм перевода алгоритмической конструкции «цикл n-раз» в рекурсивное правило.

12.           Приведите примеры задач, которые можно решить только рекурсивным алгоритмом.

13.           Дайте определение граничному условию.

14.           Приведите необходимые и достаточные условия определения граничного условия рекурсии.

15.           Дайте определение правосторонней и левосторонней  рекурсии.