Когда рекурсивная функция лучше, чем ее итерационная версия?

Question

Хорошо известно, что каждая рекурсивная функция может быть реализована в итерационной версии.

Однако рекурсивные функции, как правило, имеют некоторые накладные расходы в отношении управления стеком.

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

Answer 1

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

Основным движущим фактором при выборе рекурсии вместо итеративного подхода является сложность (т.е. время выполнения) решаемой проблемы. Каноническим примером того, как итерация массово выбивает рекурсию, является последовательность Фибоначчи.

Вычисление пятого числа Фибоначчи с использованием рекурсии требует вычисления:

f(5) = f(4) + f(3)
   f(4) = f(3) + f(2)
        f(3) = f(2) + f(1)
   f(3) = f(2) + f(1)

Выше приведено четыре рекурсивных вызова и примерно 10 оценок функций. С другой стороны, если бы мы вместо этого использовали динамическое программирование и итеративно построили Фибоначчи, нам потребовались бы только два вызова функции (оба f(1) и f(2) являются постоянными значениями 1):

f(3) = f(2) + f(1) (first call)
f(4) = f(3) + f(2) (second call)

Преимущество использования итераций становится более очевидным при вычислении больших значений последовательности Фибоначчи, например, f(100), где рекурсия взрывается из-за переполнения стека.