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