Рекурсия

Основным методом программирования в Прологе является рекурсия. Рекурсивным называется определение функции (предиката) через эту же функцию (предикат).

Рекурсивное правило в общем случае имеет следующий вид:

R:- A,U,В,R,С.

где R - предикат, определяющий рекурсивный вызов, U - предикат, определяющий условие выхода из рекурсии по неуспеху, А,В,С - группы предикатов, не влияющие на рекурсивный вызов. В процессе рекурсии предикаты группы С запоминаются и выполняются лишь по завершении рекурсии (обратный ход).

ПРОГРАММА 1.

song:- write('бегу,'),song.

Рассмотрим дерево вывода ответа на запрос:

?- write('Я '),song.

Как видно, в процессе выполнения программы возникает бесконечно длинная строка. Это пример так называемой бесконечной рекурсии ("зацикливание" программы).

Запустите программу, когда надоест любоваться красотами написания этой песни, нажмите на клавишу b для приостановки бесконечного вывода или e - для выхода из интерпретатора.

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

Рассмотрим следующий вариант программы.

ПРОГРАММА 2.

song(X):-(X>1),write('бегу,'),(Y is X - 1),song(Y).

song(1).

?-write('Я '),song(3),write('бегу по гаревой дорожке').

В данной программе используются встроенные арифметические предикаты отношения ( X > Y ) и присваивания ( X is A, где X – свободная переменная, а A - арифметическое выражение, конкретизированное числовым значением ).