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

 

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

Пример: ввод и вывод символов.

domain

char_data = char (буквы)

predicates

write_сh – написать букву

read_ сh – читать букву

goal

write_сh, read_сh.

clauses

write_сh:– write (“давай символ”), nl, nl,

write (“окончание #”), nl, nl – вывод символов

read_ сh:– readchar (Char_data), – оператор, считывающий букву с клавиатуры

Char_data <> “#”,– условие вывода из рекурсии

write (Сhar_data),

read_ сhar.

В общем случае рекурсия может быть сложной. Рассмотрим метод обобщенного правила рекурсии (ОПР):

(имя правила рекурсии):–

(список предикатов), (1)

(предикат условия выхода), (2)

(список предикатов), (3)

(имя правила рекурсии), (4)

(список предикатов), (5)

Успех или неудача любого правила из первой группы на рекурсию не влияет. В случае неудачи правила (2) происходит остановка рекурсии. Успех правила (4) вызывает повторную рекурсию.

Пример: Программа печать чисел от 1 до 7

domain

number = integer (число)

predicates

write_nmb (number)

gool

write (“это числа“), nl, nl,

write_nmb (1), nl, nl,

write (“все сделано“).

clauses

write_nmb (8). – граничные условия

write_nmb (number):–

number < 8, – условия выхода (2)

write (“ “, number), nl,

Next_ number= number+1, (3)

write_nmb (Next_ number). (4)

При вызове рекурсии имя аргумента не важно, важна позиция аргументов.

Пример: Вычисление n!

Запишем граничное условие в виде fact (0, 1).Т.е., 0!=1 – граничное условие

n! = 1*2*3*… n

Т.е. предикат записывается в виде fact (N,Y) – номер и функция

f(N)=f(N-1)*N – рекурсивное правило

n!=n*(n-1)!

fact(n, V):-M=N-1, fact(M, U), V=U*N – формула для вычисления факториала.

Рассмотрим работу Пролога на примере вычисления fact (3, X). Она состоит из двух фаз: разбиения и решения.

Первое обращение.

fact (3, X) сравнивается с fact (0, 1). Имеем 3<>0 – неудача, и используем второе правило

fact (3, X) = fact (N, V). N=3, а Х связываем с V. Тогда M = 3–1=2 и имеем fact (2, U), а Х=U*3. Пролог пытается согласовать третье правило только в случае, если согласовано второе. Поэтому проверка третьего откладывается.

Второе обращение.

Чтобы согласовать fact (2, U), сопоставляем его с набором фактов: 2<>0, из второго правила следует сопоставление fact (2, U) c fact (N2, U2) при N2=2 и U2=U, М2=2-1, fact (M2, U2),U=U2*2 – откладывается.

Третье обращение.

Согласуем последнее fact (1, U2), опять 1<>0 и N3=1, а V3=U2. Теперь согласуем m3 = 1–1=0, fact (0, U3), U2=U3*1 – откладывается.

Для M3=0 fact (0, U3) согласуется с fact (0, 1) и, следовательно, U3=1. Редукция завершена, и граничное условие позволяет ее остановить.

Теперь Пролог возвращается к отложенным условиям, согласуя их последовательно. Согласование fact (1, U2) дает U2=U3*1, так как U3=1, то U2=1. Таким образом, fact (1, U2) согласуется при U2=1. Согласование fact (2,U) – так как U=U2*2 и так как U2=1, то U=2 и fact (2, U) согласуется при U=2. Согласование fact (3, X)-так как X=U*3 и U=2, то Х=6 и fact (3, X) согласуется при Х=6.

При работе с рекурсией промежуточные значения заносятся в СТЕК. Механизм возврата начинает работать только тогда, когда в СТЕК будет занесено 9 значений. Все элементы будут по очереди выталкиваться из СТЕКа, так как любые попытки найти другие решения будут неуспешными. Таким образом, при вычислении факториалов от больших чисел СТЕК может достигать очень большой длины. Поэтому для уменьшения величины СТЕКа используют так называемую хвостовую рекурсию – рекурсию, в которой последнее условие в последнем правиле является рекурсивным. Она ограничивает рост стека благодаря очистке стека после успешного сопоставления условия, содержащего рекурсию

Пример использования хвостовой рекурсии.

predicates

fact1 (integer, real)

fac (integer, integer, real, real)

clauses

fact1 (0, 1): -!

fact1 (X, Y):– fac (X, 1, 1, Y)

fac (X, X, Y, Y,):-!

fac (X, K, P, Y): - K1=K+1, P1=P*K1, fac (X, K1, P1, Y).

Правило fac (X, K1, P1, Y) является хвостовой рекурсией.

В Прологе отсутствуют «локальные переменные» для сохранения промежуточных результатов и возможность их применения в процессе вычисления. Поэтому для реализации итерационных алгоритмов, требующих сохранение промежуточных результатов, в процедуры добавляются аргументы, называемые накопителями. Накопитель является логической переменной, а не ячейкой памяти, в процессе итерации передается не адрес, а значение. Так как логическая переменная обладает свойством одноразовости записи, то измененное значение – новая логическая переменная – передается каждый раз. Логическая переменная F, представляющая решение, должна следовать по всему вычислению, чтобы получить значение при заключительном вызове fact.

Задания для самостоятельной работы.

1. Напечатайте числа от 53 до 62

2. Напечатайте числа от 7 до 1

3. Напишите программу, которая вычисляет сумму ряда вида

S(7) = 1+3+6+...15, т.е. S(N+1) = N+1+S(N), где S(1) = 1.

4. Напишите программу, вычисляющую сумму S(15) = 1+3+5+...+15

5. Вычислите ряд f(x,n) = 1+x+x2+x3+x4+ xn

6. Напишите программу, вычисляющую степень R=XN

7. Напишите программу, вычисляющую ряд Фибоначчи