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

我正在努力解决这个问题

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 届及以后的任期问题？

请您参考如下方法:

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

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