Рекурсии в языке Prolog

Если нас интересует, является ли X предком Y, то мы должны последовательно ставить цели:

parent (X, Y).

grandparent (X, Y).

grandgrandparent (X, Y).

grandgrandgrandparent (X, Y).

и так далее, где.

grandgrandparent (X, Y): — parent (X, Z), grandparent (Z, Y).

grandgrandgrandparent (X, Y): — parent (X, Z),

grandgrandparent (Z, Y).

Вместо этого Пролог позволяет записать данное правило следующим образом:

predecessor (X, Y): — parent (X, Y).

predecessor (X, Y): — parent (X, Z), predecessor (Z, Y).

Здесь имеет место рекурсивный вызов предиката predecessor. Рекурсия в Прологе является мощным средством, позволяющим строить очень компактные и эффективные программы.

Рассмотрим использование рекурсии на примере вычисления факториала.

n! = п • (п — 1) • (п — 2) •… • 1.

Рекурсивное определение факториала: 0! = 1; n! = n х х (п — 1)! Программа на прологе, реализующая вычисление факториала будет выглядеть следующим образом:

f (0, 1).

f (N, F): — N1 = N — 1, f (N1, FI), F = FI • N.

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

Запустим программу в режиме трассировки и зададим цель f (3, X). Пролог начинает сопоставлять предикат цели с базой знаний (CALL означает вызов предиката, RETURN — завершение работы предиката, FAIL — неудачу, REDO — откат):

CALL f (3, X) цель сопоставляется с f (0, 1).

FAIL неудача, так как 3*0.

REDO f (3, X) Происходит откат на следующий экземпляр f () N = 3, Входим в тело правила. Присваиваем N = 3 N1=2 Находим N1=2 f (2, X) Пролог ставит себе подцель CALL f (2, X) которая сопоставляется с f (0, 1).

FAIL неудача, так как 2*0.

REDO f (2, X), Происходит откат на следующий экземпляр f ().

N = 2, Опять входим в тело правила. Присваиваем N = 2.

N1=1 Находим N1=1. Это уже другое N1.

f (1, X) Пролог ставит себе подцель f (1, X).

CALL f (1, X) которая сопоставляется с f (0, 1).

FAIL неудача, так как 1*0.

REDO f (1, X) Происходит откат на следующий экземпляр f ().

N = 1 Опять входим в тело правила. Присваиваем.

N = 1.

N1=0 Находим N1=0.

f (0, X) Пролог ставит себе подцель f (0, X).

CALL f (0, X) которая сопоставляется c f (0, 1).

RETURN X = 1 Успешно. Возврат из нижнего уровня рекурсии.

F = 1 Умножение 1 на 1 (факториал от 1).

RETURN X = 1 Возврат из следующего уровня рекурсии.

F = 2 Умножение 2 на 1 (факториал от 2).

RETURN X = 2 Возврат из следующего уровня рекурсии.

F = 6 Умножение 3 на 2 (факториал от 3).

RETURN X = 6 Возврат из программы Можно заметить, что логика работы программы вычисления факториала зависит от расположения в тексте предиката, определяющего выход из рекурсии. Унификация выполняется в порядке следования предикатов в тексте программы, и если предикат f (0, 1) поставить в конце, выход из рекурсии будет невозможен. Таким образом, декларативность Пролога не является абсолютной для удобства его использования. Вариант программы, в котором предикаты могут располагаться в любом порядке, представлен ниже.

f (N, F): -N>0, N1 = N — 1, f (N1, FI), F = FI • N.

f (0, 1).

Заметим также, что в данном рекурсивном предикате есть действия в теле правила после рекурсивного вызова. Это называют нарушением хвостовой рекурсии (tail recursion).

Нарушение хвостовой рекурсии, называемое также нехвостовой рекурсией, требует запоминания всего окружения рекурсивного вызова (а не только результата), поэтому приводит к большим затратам памяти. Существуют приемы устранения нехвостовых рекурсий. Ниже приведен пример вычисления факториала без нехвостовой рекурсии.

f (N1, N, FI, F): — % если N1! = F1, то N! = F

N2 = N1 + 1,.

F2 = F1*N2, % (N1 + 1)! = F2

f (N2, N, F2, F). % если N2! = F2, mo N! = F

f (N, N, F, F). % Условие выхода из рекурсии

Цель для вычисления 3! выглядит следующим образом: f (О,.

3, 1, F).

Рекурсия в Прологе не всегда используется для выполнения многократно повторяющихся действий. Вспомним базу знаний «звездной» семьи, в которой есть предикат, описывающий супружеские отношения, в частности, spouse (filipp, alia).

Супружеские отношения в отличие от родительских отношений, являются симметричными. Филипп является супругом Аллы, равно как и Алла является супругой Филиппа. При этом в предикате положение аргументов является фиксированным. Иными словами, если факт в базе знаний записан следующим образом:

spouse (filipp, alia), а предикат цели таким:

spouse (alia, filipp).

то результат будет отрицательным. Для того, чтобы показать Прологу, что это предикат является симметричным в отношении аргументов, мы можем применить правило:

spouse (X, Y): — spouse (Y, X).

В качестве примера рассмотрим известную коллизию. В деревне жили две семьи: мать с дочерью и отец с сыном. Дадим им имена. Пусть мать и дочь зовут Мария и Даша, а отца и сына Олег и Сергей соответственно. Первые буквы имен подскажут нам, кто есть кто, иначе мы запутаемся. В базе знаний эти факты найдут свое отражение в следующем виде:

parent (oleg, sergei).

parent (maria, dasha).

В силу превратностей судьбы Олег женился на Даше, и Мария вышла замуж за Сергея:

spouse (oleg, dasha).

spouse (sergei, maria).

Для симметрии супружеских отношений введем правило:

spouse (X, Y): — spouse (Y, X).

Нравы в деревне простые, поэтому жену отца положено называть мамой, а мужа матери — отцом. Правила для этого будут такими: parent (X, Y): — spouse (X, Z), parent (Z, Y).

Попробуем найти внука Сергею. Ставим цель.

grandparent (sergei, Who).

Пролог находит правило grandparent (X, Y) parent (X, Z), parent (Z, Y) и ставит себе подцель из первого предиката в теле этого правила:

parent (sergei, Z).

У Сергея детей нет, поэтому Пролог обращается к правилу parent (X, Y): — spouse (X, Z), parent (Z, Y) и ставит себе цель.

spouse (sergei, Z).

Пролог дает результат Z = maria. Второй предикат правила parent.

parent (maria, Y).

Возвращается значение Y = dasha. To есть Сергей в качестве мужа Марии числится отцом Даши. Теперь Пролог переходит ко второму предикату в правиле grandfather:

parent (dasha, Y).

Даша также не имеет детей, поэтому Пролог обращается к правилу parent (X, Y): — spouse (X, Z), parent (Z, Y) и сначала пытается найти супруга Даше:

spouse (dasha, Z).

Результат: Z = oleg. Второй предикат этого правила parent (oleg, Y) даст Y = sergei. To есть Сергей приходится внуком самому себе! Созданная нами база знаний верно отражает данную коллизию.