Рекурсивные процедуры

Классическим примером рекурсивного определения в языке Пролог может служить программа “ предок”.

Предположим, имеем дерево родственных отношений:

Создадим соответствующую базу данных “ родитель ”

родитель(пам,боб).
родитель(том,боб).
родитель(том,лиз).
родитель(боб,энн).
родитель(боб,пат).
родитель(пат, джим).

Создадим также два правила:

предок(A,B):- родитель(A,B). % (1)

предок(A,B):- родитель(С,B), предок(A, C). % (2)

Первое правило – для ближайших предков. Второе для отдаленных предков.

Любая рекурсивная процедура должна включать по крайней мере по одной из компонент:

1. Нерекурсивную фразу, определяющую исходный вид процедуры, т.е. вид процедуры в момент прекращения рекурсии.

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

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