Эффективность рекурсивных вычислений

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

Если процедура содержит единственный рекурсивный вызов и он является последним действием процедуры, то говорят, что имеет место задняя рекурсия (tail recursion) (см. процедуру Print_Front). Этот рекурсивный вызов требует затрат на создание фреймов активации и запоминание их в стеке. Когда рекурсивный вычислительный процесс доходит до условия завершения, выполняется серия возвратов, выталкивающих фреймы активации из стека. Если при наличии задней рекурсии фреймы активации не используются для окончательных вычислений, следует предпочесть итеративную реализацию (см. процедуру Print из программного модуля!!!). Рекурсивная процедура Print_Back, не содержащая задней рекурсии, имеет более эффективную реализацию, чем итеративная процедура, выполняющая те же действия.

7. Иерархические Нелинейные структуры данных. деревья