Использование рекурсии

Рекурсия – способ описания функций или процессов через самих себя. Рекурсия используется как основа для записи рекурсивных конструкций.

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

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

Введем в рассмотрение еще одно отношение –ancestor (предок). Определим его в терминах уже известного отношения parent. Отношение ancestor может быть представлено с помощью двух правил:

Правило для определения прямых предков (1);

Правило для определения отдаленных предков, то есть таких, между которыми существует цепочка родительских связей типа parent. (2)

Рис.2.4.Отношение ancestor для прямого(правило 1) и отдаленного предков(правило2)

Для всех X и Z,

1) X - предок Z, если

X – родитель Z.

Второе правило (б) формулируется так:

Для всех X и Z,

2) если имеется такой Y, что

а) X -родитель Y(прямые предки) и

б) Y –предок Z. (отдаленные предки)

Эти утверждения можно перевести на Пролог таким образом:

1) ancestor(X,Z):-

parent(X,Z).

2) ancestor(X,Z):-

parent(X,Y),

ancestor(Y,Z).

Отсюда видно (2), что было использовано утверждение ancestor, которое само еще не было полностью определено. Такие определения называются рекурсивными. Отношение, представленное в заголовке правила (2) зависит от более простой версии самого себя- от подцели ancestor(Y,Z).

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

Состав рекурсивной процедуры:

Нерекурсивное предложение (1), определяющее вид процедуры в момент ее прекращения (терминальный случай –базис рекурсии).

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