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

Рекурсия - алгоритмический метод, часто используемый при программировании на языке Пролог. Рекурсию можно применять для достижения того же эффекта, какой реализуется при употреблении итеративных управляющих конструкций, например, цикл «пока» в процедурных языках. В рекурсивном правиле более сложные входные аргументы выражаются через менее сложные. Классическим примером рекурсивного определения в Прологе может служить программа предок, состоящая из двух правил:

предок (А, В):- (1)

родитель (А, В).

предок (А, В):- (2)

родитель (С, В),

предок (А, С).

Или

предок (А, В):-

родитель (А, В).

предок (А, В):-

родитель (А,С),

предок (С, В).

Отношение, представленное в заголовке фразы (2) зависит от более простой версии самой себя - от подцели «предок».

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

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

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

Фраза (1) процедуры «предок» определяет исходный вид этой процедуры. Как только данная фраза станет истинной, дальнейшая рекурсия прекратится. Фраза (2) - это рекурсивное правило. При каждом вызове данное правило поднимается на одно поколение вверх. Подцель «родитель(С, В)», входящая в тело правила, вырабатывает значение переменной С, которое затем используется в рекурсивной подцели «предок (А, С)».

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

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