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

Другим способом реализации циклических частей программы является использование рекурсии(смотри рис.5.1.)Понятие рекурсии введено в разделе “Основы логического программирования” и использовалось в решении задачи о родственных отношениях. Ее особенность заключается в том, что вычисленные с помощью рекурсии значения передаются из одного вызова в другой как аргументы рекурсивно вызываемого предиката.

Там же были даны определения рекурсии и рекурсивности.

Когда и где применяется рекурсия?

Рекурсия применяется:

-Для решения задач, содержащих в себе подзадачи такого же типа (поиск в дереве, рекурсивная обработка (например, сортировка списков);

-работа с базами данных (БД);

-обработка файлов;

-встречаются задачи, не имеющие нерекурсивного алгоритма решения;

- в математических вычислениях.

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

Однако, существует класс рекурсивных программ, которые выполняются с использованием постоянного объема памяти. Это такие рекурсивные программы, которые могут быть преобразованы непосредственно в итерационные программы. Метод реализации таких программ называется оптимизацией хвостовой рекурсии (tail recursion optimization) (оптимизацией последнего обращения). Основная идея метода: рекурсивная программа выполняется так, как если бы она была итерационной. Когда процедура может вызвать себя без сохранения информации о своем состоянии? Это возможно в том случае, если процедура не генерирует указателей отката и последней подцелью ее является рекурсивный вызов самой себя. В этом случае информация о состоянии процедуры больше не понадобится. Получается, что когда процедура на последнем шаге вызывает саму себя, то стек для вызывающей процедуры должен быть заменен на стек для вызванной процедуры. То есть происходит при замене стека очень простая операция – аргументам процедуры присваиваются новые значения, после чего выполнение процесса возвращается на начало процедуры. Поэтому с процедурной точки зрения происходящее очень похоже на итерацию (обновление управляющих переменных в цикле).

На Прологе можно задать хвостовую рекурсию следующим образом:

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

- ранее в предложении не было точек возврата (если они есть, то от них можно избавиться с помощью отсечения, которое ставится непосредственно перед рекурсивным вызовом и помогает убрать все лишние альтернативы)

Замечание: В общем случае невозможно определить, является ли подобное отсечение зеленым или красным, поэтому надо предварительно тщательно исследовать этот вопрос.

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

Замечание:

-рекурсия логически проще метода итерации;

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