Вы всегда можете превратить рекурсивную функцию в итеративную? Да, безусловно, и тезис Черч-Тьюринга доказывает это, если память служит. Проще говоря, в нем говорится, что то, что вычислимо рекурсивными функциями, вычислимо итерационной моделью (такой как машина Тьюринга) и наоборот. Тезис не говорит вам точно, как сделать преобразование, но он говорит, что это определенно возможно.
Во многих случаях преобразование рекурсивной функции легко. Кнут предлагает несколько приемов в «Искусстве компьютерного программирования». И часто вещь, вычисленная рекурсивно, может быть вычислена совершенно другим подходом за меньшее время и пространство. Классическим примером этого являются числа Фибоначчи или их последовательности. Вы наверняка встретили эту проблему в своем плане на получение степени.
С другой стороны этой монеты мы можем, конечно, представить себе систему программирования, настолько продвинутую, чтобы рассматривать рекурсивное определение формулы как приглашение запоминать предыдущие результаты, предлагая, таким образом, преимущество в скорости без лишних усилий точно сказать компьютеру. какие шаги нужно выполнить при вычислении формулы с рекурсивным определением. Дейкстра почти наверняка представлял себе такую систему. Он провел много времени, пытаясь отделить реализацию от семантики языка программирования. Опять же, его недетерминированные и многопроцессорные языки программирования находятся в лиге выше практикующего профессионального программиста.
В конечном итоге многие функции просто легче понять, прочитать и написать в рекурсивной форме. Если нет веских причин, вам, вероятно, не следует (вручную) преобразовывать эти функции в явно итеративный алгоритм. Ваш компьютер справится с этой задачей правильно.
Я вижу одну вескую причину. Предположим, у вас есть прототип системы на языке сверхвысокого уровня, например [ надевающее асбестовое белье ] Scheme, Lisp, Haskell, OCaml, Perl или Pascal. Предположим, что условия таковы, что вам нужна реализация на C или Java. (Возможно, это политика.) Тогда вы, конечно, могли бы написать некоторые функции рекурсивно, но которые, буквально переведенные, взорвали бы вашу систему времени выполнения. Например, бесконечная хвостовая рекурсия возможна в Схеме, но та же идиома создает проблему для существующих сред Си. Другим примером является использование лексически вложенных функций и статической области видимости, которые поддерживает Pascal, но не поддерживает C.
В этих обстоятельствах вы можете попытаться преодолеть политическое сопротивление оригинальному языку. Вы могли бы плохо реализовывать Лисп, как в десятом законе Гринспуна. Или вы можете просто найти совершенно другой подход к решению. Но в любом случае, безусловно, есть выход.