Рекурсия – алгоритмический метод, часто используемый в Прологе. В рекурсивном правиле более сложные входные аргументы выражаются через менее сложные.
Классическим примером рекурсивного определения в Прологе может служить программа «Предок», состоящая из двух правил:
предок (А, В): — (1)
родитель (А, В).
предок (А, В): — (2)
родитель (С, В),
предок (А, С).

Совокупность этих правил определяет два способа, в соответствии с которыми одно лицо (А) может быть предком другого (В). Согласно первому правилу, А является предком В, если А – родитель В. Согласно второму правилу, А будет предком В, если А является предком родителя В, т.е. предком С. Отношение, представленное в заголовке второго правила, зависит от более простой версии самого себя – от подцели «предок».
Предположим, что имеется база данных «родитель»:

родитель (анна, вова).
родитель (анна, гена).
родитель (гена, витя).
родитель (витя, саша).

Нижеследующие запросы иллюстрируют
использование правила «предок»:

Является ли Анна предком Гены?
?- предок(анна, гена)
Да

Найти всех потомков Анны.
?- предок(анна, Х)
Х=вова
Х=гена
Х=витя
Х=саша

/*Программа Lab3_0.pro */

predicates
predok(symbol, symbol)
roditel(symbol, symbol)

clauses
roditel(anna, vova).
roditel(anna, gena).
roditel(gena, victor).
roditel(victor, sasha).

predok (А, В):-
roditel (А, В).
predok (А, В):-
roditel (С, В),
predok (А, С).

goal
predok (A, В).

Любая рекурсивная процедура должна содержать по крайней мере по одной из перечисленных компонент:
1) Нерекурсивную фразу, определяющую исходный вид процедуры, т.е. вид процедуры в момент прекращения рекурсии. В нашем примере это правило (1). Как только эта фраза станет истинной, дальнейшая рекурсия прекратится.
2) Рекурсивное правило. Первая подцель, располагающаяся в теле этого правила, вырабатывает новые значения аргументов. Далее размещается рекурсивная подцель, в которой используются новые значения аргументов. В нашем примере это правило (2). При каждом вызове данное правило поднимается на одно поколение вверх. Подцель родитель(С,В), входящая в тело этого правила, вырабатывает значение переменной С. Затем располагается рекурсивная подцель предок (А,С), в которой используется этот новый аргумент.

Неработоспособная версия процедуры «предок»

Назовем эту процедуру «нпредок», она отличается от процедуры «предок» лишь порядком следования подцелей в теле фразы (2):
нпредок (А, В): — (1’)
родитель (А, В).
нпредок (А, В): — (2’)
нпредок (А, С),
родитель (С, В).
С декларативной точки зрения смысл процедур «предок» и «нпредок» одинаков. Но при процедурной трактовке смысл процедур «предок» и «нпредок» существенно различается. В процедуре «предок» подцель родитель(С,В) рекурсивного правила вырабатывает новое значение переменной С, которое затем используется в рекурсивной подцели предок(А,С). С другой стороны, в процедуре «нпредок» переменная С не конкретизирована в момент обработки рекурсивной подцели нпредок(А,С). Это означает, что когда интерпретатор будет пытаться выполнить запрос к процедуре «нпредок», то сначала он отыщет правильные ответы, а затем будет выполнять рекурсивные действия вплоть до исчерпания доступного объема памяти:

?- нпредок(анна,Х)
Х=вова
Х=гена
Х=витя
Х=саша
Предупреждение: Исчерпана стековая память.

Процедура «нпредок» называется процедурой с левой рекурсией, так как во фразе (2’) рекурсивная подцель стоит первой, т.е. она расположена слева от других подцелей. Пролог не может надежно обрабатывать леворекурсивные процедуры, что объясняется заложенной в него стратегии решения задач.