поток сознанияVvicПозвольте замечания. Теоретически ДА, безусловно! Любая рекурсивная программа может быть заменена на эквивалентную ей нерекурсивную. Что на практике...
1. Да, рекурсивные алгоритмы стройны и просты для понимания и сопровождения в сравнении с нерекурсивными аналогами.
2. Но! Накладные расходы на вызов почти во всех современных архитектурах несравнимо больше,чем при локальной передаче управления. А в таких сложных архитектурах, как архитектуры семейства EPIC (IA64, E-3M, etc.) это разница еще заметнее.
3. Хороший компилятор в состоянии выполнить преобразование хвостовой рекурсии (tail recursion), что может существенно повысить эффективность кода. Попробуйте хотя бы написать вычисление факториала через рекурсию, а затем переписать с помощью внутрипроцедурного цикла (как это бы сделал компилятор). Разницу в скорости выполнения вы почувствуете и без утилиты time. Вся исключительность этого частного случая (tail recursion) в том, что как не требует стека: live-range никакого объекта не переживает точку рекурсивного вызова. Это на заметку тем, кто пишет, что Рекурсия - это, по сути, стек. Хотя, в общем случае, они правы.
4. На практике tail recursion срабатывает крайне редко. Подумайте хотя бы над тем, как преобразовывать в нерекурсивный вид вычисление функции Аккермана - она занимает 5 строчек, но содержит два рекурсивных вызова. Если поняли, попробуйте подумать над тем, как научить этому компилятор. Это непросто.
5. Дальше все еще хуже: рекурсия далеко не всегда бывает прямой f( ) f( ). Для случая f( ) g( ) f( ) еще можно подумать об inline-подстановке. Когда же длина рекурсивного цикла составляет 3-4-5-... функций, ситуация усложняется колоссально. Но и это еще не самое страшное. Вход в рекурсивный цикл (читай: сильно-связная компонента графа вызовов программы) может осуществляться не через одну функцию, другими словами, у рекурсивного цикла может быть множество голов. Вообще, на практике, рекурсивные циклы, как правило, не являются сводимыми, а цена за сведение, как и во внутрипроцедурном случае - многократное дублирование кода. Добавьте к этому такую возможность современных языков программирования, как вызов по косвенности и факт возникновения рекурсии вообще может стать очевидным только во время исполнения. Хорошо, если в этом случае вас спасет девиртуализация... Я еще знаю пару серьёзных препятствий на пути избавления от рекурсии...
6. Самое ужасно, что иногда, несмотря на все описанные (и неописанные) проблемы, от рекурсии необходимо избавляться во чтобы то ни стало. Будучи сотрудником Intel Compiler Lab, я полгода потратил на переписывание рекурсивных алгоритмов в компиляторе, так как на стресс-тестах компилятор высаживал стек. Рекурсия - красивая языковая конструкция, но в приложениях, надежность которых критичная, использовать ее надо исключительно аккуратно!!

http://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=927349&msg=12289896 ShSergeЕсли юный неофит начнёт изучать вэб-технологии с какого-то фреймворка, а базы данных с ОРМа, то мои умения будут ещё долго востребованы. :)