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

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

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

ким другим образом.

- Она логически проще метода итерации.

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

Рекурсия - хороший способ для описания задач, содержащих в себе под-

задачу такого же типа. Например, поиск в структуре дерева (дерево состав-

ляется из более мелких деревьев) и рекурсивная сортировка (сортировка

списков, разделение их на части, сортировка частей и составление их вмес-

те).

Логически, рекурсивным алгоритмам присуща структура индуктивного ма-

тематического доказательства. Предыдущая рекурсивная программа вычисления

факториала CH07EX03.PRO описывает бесконечное множество различных вычис-

лений с помощью всего лишь двух предложений. Кроме того, о правильности

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

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

У рекурсии есть один большой недостаток - она съедает память. Всякий

раз, когда одна процедура вызывает другую, информация о выполнении вызы-

вающей процедуры должна быть сохранена для того, чтобы она (вызывающая

процедура) могла, после выполнения вызванной процедуры, возобновить вы-

полнение на том же месте, где остановилась. Это означает, что если проце-

дура вызывает себя 100 раз, то 100 различных состояний должно быть запи-

сано сразу. (Состояния решения сохраняются в стековой структуре (stack

frame).) Память IBM PC способна поместить от 3000 до 4000 стеков. А что

вы станете делать, если захотите повторить что-либо более 4000 раз?

Это исключает наличие специального случая, когда процедура может

вызвать себя без сохранения информации о своем состоянии. А, что если вы-

зывающая процедура не собирается возобновлять работу после выполнения

вызванной процедуры?

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

ванная процедура завершит работу, вызывающая процедура не должна больше

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

состояние, потому что эта информация уже не понадобится. Как только выз-

ванная процедура завершится, работа процессора должна идти в направлении,

указанном для вызывающей процедуры после ее выполнения.

Например, допустим, что процедура А вызывает процедуру В, а В вызы-

вает С в качестве своего последнего шага. Когда В вызывает С, В не должно

больше ничего делать. Поэтому, вместо того, чтобы сохранить для С текущее

состояние о процедуре В, вы можете переместить информацию из стека В (ко-

торый больше не нужен) в текущий стек С. Когда С закончит выполнение, она

будет считаться вызванной непосредственно процедурой А.

А сейчас предположим, что на последнем шаге выполнения процедура В,

вместо процедуры С вызывает себя. Рецепт говорит, что когда В вызывает В,

стек для вызывающей В должен быть заменен стеком для вызванной В. Это

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

и возвратом процессора к началу процедуры. Поэтому, для процедуры это оз-

начает лишь обновление управляющих переменных в цикле.

Эта операция называется оптимизацией хвостовой рекурсии или оптими-

зацией последнего вызова.