Рекурсия с памятью против цикла

Question

Я сделал две функции для вычисления последовательности Фибоначчи, одну с использованием рекурсии с памятью и одну с использованием цикла;

def fib_rec(n, dic = {0 : 0, 1 : 1}):
    if n in dic:
        return dic[n]
    else:
        fib = fib_rec(n - 2, dic) + fib_rec(n - 1, dic)
        dic[n] = fib
        return fib
    

def fib_loop(n):
    if n == 0 or n == 1:
        return n
    else:
        smaller = 0
        larger = 1
        for i in range(1, n):
            smaller, larger = larger, smaller + larger
        return larger

Я слышал, что последовательность Фибоначчи часто решается с использованием рекурсия, но мне интересно, почему. Оба моих алгоритма имеют линейную временную сложность, но тот, который использует al oop, не должен содержать словарь всех прошлых чисел Фибоначчи, он также не будет превышать глубину рекурсии Python.

Эта проблема решена с использованием рекурсии только для обучения рекурсии, или я что-то упустил?

Answer 1

Обычная рекурсивная реализация Фибоначчи O (N) больше похожа на это:

def fib(n, a=0, b=1):
    if n == 0: return a
    if n == 1: return b
    return fib(n - 1, b, a + b)

Преимущество этого подхода (помимо того факта, что он использует память O (1)) состоит в том, что это хвост -recursive: некоторые компиляторы и / или среды выполнения могут воспользоваться этим, чтобы тайно преобразовать его в простую инструкцию JUMP. Это называется оптимизацией хвостового вызова.

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

Последовательность Фибоначчи - в основном игрушечная задача, используемая для обучения людей написанию алгоритмов и большой нотации Oh. Он имеет элегантные функциональные решения, а также демонстрирует сильные стороны динамического c программирования (в основном ваше решение на основе словаря), но это также практически решенная проблема.

Мы также можем go намного быстрее. На странице https://www.nayuki.io/page/fast-fibonacci-algorithms описано, как это сделать. Он включает в себя алгоритм быстрого удвоения, написанный на Python, который я хотел бы включить сюда, но, к сожалению, лицензия не позволяет мне это сделать.