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

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

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

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

Математическая запись

Запись на Prolog

Граничное условие

S0=0

sum(0,0).

Общее или рекурсивное условие

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

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

  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. Дайте определение правосторонней и левосторонней рекурсии.