python - 斐波那契程序在第 40 个任期后挂起

Question

我正在努力解决这个问题

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Link: https://projecteuler.net/problem=2

下面是我必须计算斐波那契数的代码:

# fibonacci series
def fib(x):
    if x==0 or x==1:
        return 1                         
    else:
        return fib(x-1) + fib(x-2)

def test_fib(n):
    for i in range (n+1):
        print 'fib of', i, ' = ' , fib(i)

test_fib(41)

但是，程序在第 40 个任期后挂起。这段代码有什么问题，如何解决第 40 届及以后的任期问题？

Answer 1

斐波那契算法的朴素递归实现会很快变慢。有两种方法可以解决此问题:

a) 切换到迭代版本

def fib(x):
    if x==0 or x==1:
        return 1                         
    a = b = 1
    for _ in range(x-1):
        a, b = b, a+b
    return b

这不如递归解决方案优雅，但具有线性时间复杂度。

b) 使用内存:

from functools import lru_cache

@lru_cache()
def fib(x):
    if x==0 or x==1:
        return 1                         
    else:
        return fib(x-1) + fib (x-2)

这是递归的解决方案，但带有“内存”。如果您必须多次调用该函数，它还有一个比迭代版本更快的额外好处。

在旧版本的 Python 中(例如 2.7)，lru_cache 还不存在，但是你实现了一个足够我们使用的廉价副本:

def lru_cache():
    # second-order decorator to be a drop-in replacement
    def decorator(fn):
        cache = {}
        def wrapped(*args, **kwargs):
            if args in cache:
                return cache[args]
            val = fn(*args)
            cache[args] = val
            return val
        return wrapped
    return decorator