Методы организации рекурсии

Метод повтора, использующий бесконечный цикл

Вид правила повторения, порождающего бесконечный цикл:

repeat.

repeat:- repeat.

Первый repeat является предложением, объявляющим предикат repeat истинным. Однако, поскольку имеется еще один вариант для данного предложения, то указатель возврата устанавливается на первый repeat. Второй repeat – это правило, которое использует само себя как компоненту (третий repeat). Второй repeat вызывает третий repeat, и этот вызов вычисляется успешно, так как первый repeat удовлетворяет подцели repeat. Предикат repeat будет вычисляться успешно при каждой новой попытке его вызвать после возврата. Факт будет использоваться для выполнения всех подцелей. Таким образом, repeat это рекурсивное правило, которое никогда не бывает неуспешным. Предикат repeat широко используется в качестве компонента других правил, который вызывает повторное выполнение всех следующих за ним компонентов.

Пример 47: ввести с клавиатуры целые числа и вывести их на экран. Программа завершается при вводе числа 0.

domains

d=integer

predicates

repeat

write_decimal

do_echo

check (d)

clauses

repeat.

repeat:- repeat.

write_decimal:-nl, write( «Введите, пожалуйста, цифры»), nl,

write(«Я повторю их»), nl,

write(«Чтобы остановить меня, введите 0»), nl, nl.

do_echo:- repeat, readln (D), write(D), nl, check (D), !.

check (0):- nl, write («-OK!»).

check(_):- fail.

goal

write_decimal, do_echo.

Правило do_echo – это конечное правило повтора, благодаря тому, что предикат repeat является его компонентом и вызывает повторение предикатов readln, write, и check. Предикат check описывается двумя предложениями. Первое предложение будет успешным, если вводимая цифра 0, при этом курсор сдвигается на начало следующей строки и на экране появляется сообщение «OK!» и процесс повторения завершается, так как после предиката check в теле правила следует предикат отсечения. Если введенное значение отличается от 0, то результатом выполнения предиката check будет fail в соответствии со вторым предложением. В этом случае произойдет возврат к предикату repeat. Repeat повторяет посылки в правой части правила, находящиеся правее repeat и левее условия выхода из бесконечного цикла.

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

Например, в приведенной ниже программе вычисления факториала (пример 48), приведен пример написания рекурсивного предиката. При этом Пролог создает новую копию предиката factorial таким образом, что он становится способным вызвать сам себя как самостоятельную процедуру.