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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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