为什么Python递归如此昂贵?我们能做些什么呢?

2022-04-12 00:00:00 python 递归 stack-overflow c++

假设我们要计算一些模为997的斐波纳契数。

对于n=500,我们可以在C++中运行

#include <iostream>
#include <array>

std::array<int, 2> fib(unsigned n) {
    if (!n)
        return {1, 1};
    auto x = fib(n - 1);
    return {(x[0] + x[1]) % 997, (x[0] + 2 * x[1]) % 997};
}

int main() {
    std::cout << fib(500)[0];
}

和在Python中

def fib(n):
    if n==1:
        return (1, 2)
    x=fib(n-1)
    return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)

if __name__=='__main__':
    print(fib(500)[0])

两者都将毫无问题地找到答案996。我们正在使用模数来保持合理的输出大小,并使用对来避免指数分支。

对于n=5000,C++代码输出783,但Python将出现错误

RecursionError: maximum recursion depth exceeded in comparison

如果我们添加几行

import sys

def fib(n):
    if n==1:
        return (1, 2)
    x=fib(n-1)
    return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)

if __name__=='__main__':
    sys.setrecursionlimit(5000)
    print(fib(5000)[0])

然后,Python也会给出正确的答案。

forn=50000当Python崩溃时(至少在我的计算机上),C++在毫秒内找到答案151。

为什么递归调用在C++中要便宜得多?我们是否可以通过某种方式修改Python编译器,使其更易于接受递归?

当然,一种解决方案是用迭代代替递归。对于斐波纳契数来说,这很容易做到。然而,这将交换初始条件和终止条件,而后者对于许多问题(例如,阿尔法-贝塔修剪)来说是棘手的。因此,一般来说,这将需要程序员进行大量艰苦的工作。


解决方案

解决方案是一个蹦床:递归函数不是调用另一个函数,而是返回一个函数,该函数使用适当的参数进行调用。有一个更高一级的循环,它在一个循环中调用所有这些函数,直到我们得到最终结果。我可能没有很好地解释它;您可以在网上找到更好的资源。

关键是这会将递归转换为迭代。我不认为这更快,也许更慢,但递归深度仍然很低。

实现可能如下所示。为清楚起见,我将x拆分为ab。然后,我将递归函数转换为跟踪ab作为参数的版本,使其成为尾递归函数。

def fib_acc(n, a, b):
    if n == 1:
        return (a, b)
    return lambda: fib_acc(n - 1, (a+b) % 997, (a+2*b) % 997)

def fib(n):
    x = fib_acc(n, 1, 2)
    while callable(x):
        x = x()
    return x

if __name__=='__main__':
    print(fib(50000)[0])

相关文章