python - 递归计算斐波那契数列的计算效率最高的方法是什么？

Question

这是我目前拥有的代码。

def fibonacci(n):

    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        value = fibonacci(n - 1) + fibonacci(n - 2)
        return value

目前计算大于 n = 30 的值需要相当长的时间。是否有计算效率更高的方法来完成此任务？

Answer 1

添加值缓存以换取一些内存以减少处理时间可能是一种有用的方法。纯粹的递归程序将尝试一遍又一遍地计算值，但是对于较大的值，这需要时间。如果这些值没有改变，那么存储它们会很有帮助。但值得注意的是，如果值不稳定，您可能需要采用不同的方法。

fibonacci_value_cache = {}


def fibonacci(n):

    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in fibonacci_value_cache:
        return fibonacci_value_cache[n]
    else:
        fibonacci_value_cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
        return fibonacci_value_cache[n]

n = 100

print("Fib " + str(n) + ": " + str(fibonacci(n)))

这里，我们检查该值是否在字典中，如果是则返回，否则我们计算它并将其添加到字典中。这意味着我们可以通过不多次计算相同的值来更好地利用处理器。