Рекурсия.

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

Используемое программное обеспечение: Visual Prolog 5.2.

Теоретические сведения

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

Базис рекурсии - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу даже без использования рекурсии. Так, в процедуре, описывающей предикат предок, базисом рекурсии является первое правило, в котором определено, что бли­жайшими предками человека являются его родители. Это предложе­ние часто содержит условие, при выполнении которого происходит выход из рекурсии или отсечение.

Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката. Если мы хотим избежать зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Пара­метры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, разме­щенное в самом правиле. В общем виде правило, реализующее шаг рекурсии, будет выглядеть так:

< имя определяемого предиката>: -

[< подцели> ],

[< условие выхода из рекурсии> ],

[< подцели> ],

< имя определяемого предиката>,

[< подцели> ].

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

Рекурсия обычно применяется при обработке списков, строк (например, для поиска и замены подстроки), при вычислениях (например, вычисление сумм, факториала) и в ряде других случаев.

Преимущества рекурсии

Рекурсия имеет три главных преимущества:

- может выразить алгоритмы, которые не могут удобно быть выражены никаким другим путем;

- логически более проста, чем повторение;

- используется экстенсивно в обработке списка.

Рекурсия - естественный способ описать любую проблему, которая содержит в пределах себя другую проблему того же самого вида.

Оптимизация обратной рекурсии

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

Оказывается, что есть специальный случай, в котором процедура может вызвать себя, не храня состояние выполнения. Что, если процедура запроса не собирается возобновлять после вызванных концов процедуры?

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

Например, процедура вызвала B, и B вызывает процедуру C как ее самый последний шаг. Когда B вызывает C, B не собирается делать что-нибудь еще. Так, вместо того, чтобы хранить текущее состояние выполнения для C под B, можно заменить старое сохраненное состояние B, которое не необходимо больше, текущим состоянием C, делая соответствующие изменения в сохраненной информации. Когда кончится C, она думает, что ее вызывали непосредственно.

Теперь предположим что вместо того, чтобы вызвать C, процедура B вызывает себя как самый последний шаг. Когда B вызывает B, структура стека для запроса B должна быть заменена структурой стека для вызванного B. Это особенно простое действие; только аргументы должны быть установлены на новые величины. Так, с процедурной точки зрения, то, что случается, очень похоже на обновление переменных контроля в цикле.

Это называют оптимизацией обратной рекурсии или оптимизацией последнего запроса. Обратите внимание на то, что по техническим причинам, рекурсивные функции (предикаты, возвращающие величины) не могут быть так оптимизированы.

Давайте рассмотрим следующие примеры рекурсии.

Пример 1.

Имеется база данных, которая содержит следующие факты:

roditel(ivan, oleg). % иван является родителем олега

roditel(inna, oleg). % инна является родителем олега

roditel(oleg, dima). % олег является родителем димы

roditel(oleg, marina). % олег является родителем марины

Составить рекурсивное правило предок и определить всех предков и их потомков.

Решение:

1. Описание раздела доменов. Дадим имя аргументу - name и определим его тип.

name=string

2. Назовем предикаты: roditel и predok, которые будут иметь по два аргумента - name.

nondeterm roditel(name, name)

nondeterm predok(name, name)

3. Теперь составим правила. Обозначим аргументы предикатов (roditel, predok) как Х, У, Z.

Исходя из данной нам базы данных, составим правила таким образом, чтобы предикаты меняли свои объекты местами:

predok(X, Z): - roditel(X, Z).

predok(X, Z): - roditel(X, Y), predok(Y, Z).

4. Для того, чтобы Пролог вывел результат: всех предков и его потомков, опишем цель predok(X, Y). Стандартный предикат write - выводит аргументы, заключенные в кавычки. Предикат fail - предикат возврата.

В общем виде программный код данного примера выглядит так: