在对递归函数进行了一些研究之后，我面临着一个矛盾：一方面以递归的方式解决问题很优雅，而另一方面在实践中性能似乎很糟糕，并且递归调用的数量有限。

我了解默认情况下，Python的递归深度限制为1000，但是即使在简单的应用程序中，我也会在40至50次调用时获得非常差的性能。

让我举个例子：

def fibonacci(n):
    if n == 1 or n == 0:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

我的PC上的这个简单的递归函数即使花费很低的n也要花费大量的时间来解决。为了测试，我还编写了另一个函数：

def fib_nonrecursive(n):
    fib_seq = [1, 1]
    for i in range(2, n+1):
        value = fib_seq[i-1] + fib_seq[i-2]
        fib_seq.append(value)        
    return fib_seq[i]

即使在大数上，非递归方式也非常快，因此，确定的问题不会涉及运算或数字大小。所以我的问题是为什么递归方法这么慢并且有什么方法可以使它更快？有没有办法扩大复活深度？

编辑 由于答案建议使用记忆，所以我研究了它并在示例中实现了它：

def mem(f):
    memory = {}
    def inner_function(x):
        if x not in memory:            
            memory[x] = f(x)
            return memory[x]
        else:
            return memory[x]
    return inner_function

@mem
def fibonacci(n):
    if n == 1 or n == 0:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

同样mem(f)可以与其他递归函数一起使用f。该@mem部分必须包括在内，f以作为参数传递给mem()（请参阅“装饰器”）。这是一种稍微先进的编码方式，但我发现对于给定的示例，实现备忘录是一件容易的事。如果有更简单的实现方法，请指正。