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

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

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

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

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

Математическая запись	Запись на Prolog
Граничное условие
S₀=0	sum(0,0).
Общее или рекурсивное условие
S_n=S_n-1 + n	sum(N,S) if N1=N-1, sum(N1, S1), S=S1+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) станет истиной при выполнении запроса, то процесс рекурсии прекращается.

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

Определим процедуру 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

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

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".

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

Дайте определение рекурсии.
Приведите примеры художественной, литературной рекурсии.
Что является более общим понятием рекурсия или цикл?
Дайте определение косвенной рекурсии.

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

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).

Какие ответы выдаст система?

Дана база данных, содержащая факты
```
путешествия(Компания,Отправление,Прибытие,Вид транспорта).
```
Определить рекурсивную процедуру можно_путешествовать из города А в город В.
Опишите иерархическую феодальную лестницу от короля до рыцаря. Напишите процедуру, определяющую, кто встанет под знамена короля в ответ на его призыв собраться.
В каких случаях следует применять конструкцию «повтор … отказ»?
Разработайте алгоритм перевода алгоритмической конструкции «цикл пока» в рекурсивное правило.
Разработайте алгоритм перевода алгоритмической конструкции «цикл до» в рекурсивное правило.
Разработайте алгоритм перевода алгоритмической конструкции «цикл n-раз» в рекурсивное правило.
Приведите примеры задач, которые можно решить только рекурсивным алгоритмом.
Дайте определение граничному условию.
Приведите необходимые и достаточные условия определения граничного условия рекурсии.
Дайте определение правосторонней и левосторонней рекурсии.