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

Метод повтора, определяемый пользователем

Вид правила повторения, определяемого пользователем:

repeat.

repeat:- repeat.

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

Пример 30: ввести с клавиатуры целые числа и вывести их на экран. Программа завершается при вводе числа 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.

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

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

Пример 31: показать, что любое целое положительное число является натуральным числом.

predicates

p (integer)

n (integer)

clauses

р(1).

p(Х):-Y=X-1, p(Y).

n(X):-p(X).

goal

n(3).

Дерево решения можно изобразить в следующем виде:

Условием выхода в данном примере служит факт p (1).

Пример 32: написать программу вычисления факториала.

predicates

factorial (integer, integer)

clauses

factorial (1, 1):-!.

factorial (N, R):- N1=N-1, factorial (N1, R1), R=N*R1.

goal

f (7, Result).

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

Пример 33: написать программу, генерирующую числа Фибоначчи до заданного значения.

predicates

f (integer, integer)

clauses

f (1, 1).

f (2, 1).

f(N, F):- N1=N-1, f (N1, F1), N2=N1-1, f (N2,F2), F=F1+F2.

goal

f (10, Fib).

Дата добавления: 2015-06-27