python - 有什么方法可以使递归函数更快吗？

Question

经过对递归函数的一些研究后，我面临着矛盾:一方面以递归方式解决问题很优雅，但另一方面在实践中性能似乎很糟糕并且递归调用的数量是有限的。

我知道默认情况下 Python 的递归深度限制为 1000，但是即使在一个简单的应用程序中，早在 40 - 50 次调用时我的性能就非常糟糕。

举个例子:

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

我的电脑上的这个简单的递归函数即使对于低 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()(请参阅“装饰器”) 这是稍微先进的编码方式，但我没有找到更简单的方法来为给定的示例实现记忆化。如果有更简单的实现方式请指正。

Answer 1

忽略 fibonacci() 是记忆化的教科书案例(这会使其速度更快)这一事实，“深度且廉价”的递归在普通 Python 中根本不是一个东西。

在许多语言中都存在尾调用消除。 Python没有这个。在许多语言中，推送额外的堆栈帧非常便宜。在 Python 中并非如此。

要找到存在问题的实际代码并不容易，这可能在某种程度上解释了为什么 Python 人员保持简单并始终创建具有完整调试能力的真正堆栈框架。大多数 Python 应用程序中对廉价和深度递归的需求并不多。