что издержки на рекурсию больше,

То, что издержки на рекурсию больше, чем на ите­рацию, связано с дополнительными командами, затрачиваемыми на вход в процедуру и выход из нее. Некоторые компиляторы пытаются выполнить оп­тимизацию, называемую оптимизацией хвостовой рекурсии (tail-recursion) или оптимизацией последнего вызова (last-call). Если единственный рекурсивный вызов в процедуре — последний оператор процедуры, то можно автома­тически перевести рекурсию в итерацию.

Размер стека

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

   Однако при применении рекурсии размер стека во время выполнения тео­ретически неограничен:

C

i = get(); 

j = factorial(i);

В упражнениях приведена функция Акерманна, которая гарантированно пе­реполнит любой стек! Но на практике обычно нетрудно оценить размер сте­ка, даже когда используется рекурсия. Предположим, что размер записи ак­тивации приблизительно равен 10, а глубина рекурсии не больше несколь­ких сотен. Добавления к стеку лишних 10 Кбайт более чем достаточно.

    Читатели, которые изучали структуры данных, знают, что рекурсией удобно пользоваться при работе с древовидными структурами в таких алго­ритмах, как быстрая сортировка и приоритетные очереди. Глубина рекур­сии в алгоритмах обработки древовидных структур данных — приблизи­тельно Iog2 от размера структуры. Для реальных программ глубина рекур­сии не превышает 10 или 20, поэтому опасность переполнения стека очень невелика.

    Независимо от того, используется рекурсия или нет, сама природа рассматриваемых систем такова, что потенциально возможное перепол­нение стека должно как-то обрабатываться.

Содержание  Назад  Вперед

---