Жалко что на форуме нет ни одного теоретика из этой области.
Ok! Давайте поговорим о теории
Для пояснения своей точки зрения на заданный вопрос начну с цитат из широко известных классиков:
Цитата:
“Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.” Н. Вирт, Алгоритмы+структуры данных = программы, М.: Мир, 1985, С.151.
“Процедура является рекурсивной, если ее новая активация может начаться до того, как завершилась ее более ранняя активация” Ахо А., Сети Р., Ульман Дж., Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2003, C.378.
“Рекурсивные алгоритмы наиболее пригодны в случаях, когда поставленная задача или данные определены рекурсивно.” Н. Вирт, С. 153.
“Итак, вывод таков: следует избегать рекурсии, когда имеется очевидное итеративное решение поставленной задачи. Но это не значит, что всегда нужно избавляться от рекурсии любой ценой. […] Тот факт, что рекурсивные процедуры можно реализовать на не рекурсивных по сути машинах[bold -- bin], говорит о том, что для практических целей любую рекурсивную программу можно преобразовать в чисто итеративную. Но это требует явного манипулирования со стеком рекурсий, и эти операции до такой степени заслоняют суть программы, что понять ее становится очень трудно. Следовательно, алгоритмы, которые по своей природе скорее рекурсивны, чем итеративны, нужно представлять в виде рекурсивных процедур.” Н. Вирт, С. 155-156.
Продолжим практикой. Чтобы ознакомиться с конкретной всем известной реализацией в железе на Интеловских CPU до Pentium-4 включительно, можно прочитать и главу 15 учебника
В.И. Юров, Assembler, 2-ое изд., СПб.: Питер, 2004. Там про процедуры и их реализацию на языке ассемблера. Сразу станет видно, что имел в виду Вирт, говоря о “не рекурсивных по сути машинах”. Если допустить незначительные упрощения, то можно сказать, что на уровне объектного кода, т.е. инструкций CPU, различия между рекурсией и итерацией сходят на нет – т.е. практически дело сводится к тому, доверяет программист компилятору составить список действий со стеком или же хочет сделать это собственноручно.
В процитированной выше книге Вирт не советует рекурсивно вычислять факториал. В заметке
M.Trofimov, How Much Does a Recursion Cost? // J.of Pascal, Ada & Modula-2, Vol. 9, 1990, No. 3, p.6 я это сделал на IBM PC AT/MS DOS/Turbo Pascal 3.3 и сравнил по времени с итеративным решением – получилось не только не хуже, а даже чуть лучше. В уже сугубо научном журнале предложил оптимизацию (на рекурсивной процедуре) так называемого индекса Хосои (полное число паросочетаний молекулярного графа
) – см.
M.Trofimov, An Optimization of Procedure for Calculation of Hosoya's Index. // J of Mathematical Chemistry, 1991, No. 8, p. 327. А позже предложил эффективный алгоритм (рекурсивный с возвратом) для тестирования в СУБД молекулярных графов на изоморфизм:
М.И. Трофимов, Е.А. Смоленский, Применение индексов электроотрицательности органических молекул в задачах химической информатики. // Известия РАН, сер.хим., 2005, №9, c. 2166. До сих пор получаю отзывы, но претензий к рекурсии еще не было
Но может, у меня слишком особые задачи? Опять вернусь к классике. Вирт в своих книгах не только утверждал, что если структура данных рекурсивная, то и алгоритм, работающий с ней, удобнее делать рекурсивным, но и применил это на практике в компиляторах. И посмотрев классические компиляторы с открытым кодом, мы можем видеть, как эффективно они осуществляют грамматический разбор с применением рекурсии. При том, что рекурсия заменяется итерацией на уровне генерации объектного кода. И за Виртом пошли другие разработчики компиляторов…
Вывод простой: не заморачиваться без особых причин и не верить мифам, берущим исток с раннего фортрана и бейсика (где рекурсия не поддерживалась; не сравнивать с современным VBA!), а также не пытаться конкурировать с компилятором: современные компиляторы умеют работать со стеком гораздо лучше людей. Рекурсивный алгоритм и рекурсивная программа не хуже итеративных при прочих равных.
