Рекурсия в Prolog: предки

Урок о том, как одно правило, ссылающееся само на себя, описывает связи любой глубины — на примере предков.

Рекурсивное правило — правило, в теле которого встречается тот же предикат, что и в заголовке; оно сводит большую задачу к такой же, но меньшей.

Зачем рекурсия

Фактами parent/2 мы описываем связь на один шаг: кто чей непосредственный родитель. Но «предок» — это родитель, или дедушка, или прапрабабушка, то есть цепочка parent неизвестной заранее длины. Перечислить все варианты («родитель родителя», «родитель родителя родителя»…) невозможно. Рекурсия решает это элегантно: мы определяем предка через самого предка и тем самым покрываем цепочки любой глубины одним правилом.

База и два предложения

Та же семья, что и в прошлом уроке:

parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).

Определение предка состоит из двух предложений — базового и рекурсивного:

% Базовый случай: родитель — это предок.
ancestor(X, Z) :- parent(X, Z).

% Рекурсивный случай: X — предок Z, если X родитель некоего Y,
% а Y — предок Z.
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).

Базовый случай

Первое предложение — «дно» рекурсии. Оно останавливает спуск: если X прямой родитель Z, дальше углубляться не нужно. Без базового случая рекурсия никогда не завершилась бы.

Рекурсивный случай

Второе предложение делает шаг к цели: берём родителя Y для X и спрашиваем, не предок ли Y для Z. Промежуточный Y — это «мостик» на одно поколение. Каждый рекурсивный вызов укорачивает оставшуюся цепочку на один parent, поэтому рано или поздно сработает базовый случай.

Как идёт вывод

Спросим, предок ли Tom для Jim:

?- ancestor(tom, jim).

Prolog пробует предложения сверху вниз. Базовый случай parent(tom, jim) — такого факта нет, провал. Берём рекурсивное предложение: parent(tom, Y) даёт Y = bob, дальше нужно ancestor(bob, jim). Это снова ancestor, но с другим первым аргументом — спуск:

ancestor(tom, jim)
  | parent(tom, Y=bob)
  ancestor(bob, jim)
    | parent(bob, Y=pat)
    ancestor(pat, jim)
      | базовый случай: parent(pat, jim) -- ЕСТЬ!
      успех

На каждом уровне цель сокращается, пока на ancestor(pat, jim) не сработает базовое предложение parent(pat, jim). Успех «поднимается» обратно по цепочке вызовов:

Вывод:

true.

Заметьте: по пути parent(bob, Y) сначала пробовал Y = ann, упирался в тупик (ann — не предок Jim) и через бэктрекинг переходил к Y = pat. Рекурсия и бэктрекинг работают рука об руку.

Все потомки одним запросом

Рекурсивное правило прекрасно работает «в обе стороны». Спросим всех потомков Tom:

?- ancestor(tom, Z).
Z = bob ;
Z = liz ;
Z = ann ;
Z = pat ;
Z = jim ;
false.

Сначала базовый случай выдаёт прямых детей (bob, liz), затем рекурсивный спускается глубже и находит внуков и правнука.

Как работает под капотом

Каждый рекурсивный вызов — это новый кадр на стеке вычислений со своими копиями переменных. Y на уровне ancestor(tom, ...) и Y на уровне ancestor(bob, ...) — разные переменные, они не мешают друг другу. Сборка ответа идёт сверху вниз при спуске и «разворачивается» обратно при подъёме, когда базовый случай вернул успех.

Частые ошибки

Порядок предложений: базовый случай первым

Базовое предложение принято ставить перед рекурсивным. Так Prolog сначала проверяет «дно», быстрее находит короткие ответы и реже уходит в глубокий спуск. Это вопрос эффективности и порядка решений.

Левая рекурсия и зацикливание

А вот порядок целей внутри тела рекурсивного предложения критичен. Сравните правильный вариант с опасным:

% ПЛОХО -- левая рекурсия: рекурсивный вызов стоит ПЕРВЫМ.
ancestor(X, Z) :- ancestor(X, Y), parent(Y, Z).

Здесь Prolog сразу вызывает ancestor(X, Y) с несвязанными переменными, тот снова вызывает ancestor(X, Y), и так до бесконечности — программа зависает или падает по переполнению стека, ни разу не дойдя до parent. Это левая рекурсия. В правильной версии первым стоит конкретизирующий вызов parent(X, Y): он связывает Y реальным значением и гарантирует, что каждый шаг укорачивает задачу.

• Забыть базовый случай — рекурсия не имеет «дна» и не завершается.
• Поставить рекурсивный вызов первым в теле — левая рекурсия, зацикливание.
• Думать, что переменные общие между уровнями — у каждого вызова свои.

Итог

• Рекурсивный предикат состоит из базового случая (останов) и рекурсивного (шаг к цели).
• ancestor описывает связь любой глубины через цепочку parent.
• Каждый рекурсивный вызов сокращает задачу и имеет свои копии переменных.
• Базовое предложение ставят первым; внутри тела конкретизирующий вызов должен идти перед рекурсивным.
• Левая рекурсия (рекурсивный вызов первым) приводит к зацикливанию.