python - 为什么 Python 递归如此昂贵，我们能做些什么？

Question

假设我们要计算一些斐波那契数，以 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 也会给出正确的答案。
对于 n=50000当 Python 崩溃时(至少在我的机器上)，C++ 在几毫秒内找到了答案 151。
为什么递归调用在 C++ 中如此便宜？我们能否以某种方式修改 Python 编译器以使其更容易接受递归？
当然，一种解决方案是用迭代代替递归。对于斐波那契数列，这很容易做到。然而，这将交换初始条件和终止条件，后者对于许多问题(例如 alpha-beta 剪枝)来说很棘手。所以一般来说，这需要程序员付出很多努力。

Answer 1

一个解决方案是蹦床:递归函数不是调用另一个函数，而是返回一个函数，该函数使用适当的参数进行调用。有一个更高一级的循环在循环中调用所有这些函数，直到我们得到最终结果。我可能没有很好地解释它；您可以在网上找到做得更好的资源。
关键是这将递归转换为迭代。我不认为这更快，甚至可能更慢，但递归深度保持较低。
一个实现可能如下所示。我分了对 x进入 a和 b为了清楚起见。然后我将递归函数转换为跟踪 a 的版本。和 b作为参数，使其尾递归。

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])