Python 递归次数和性能问题优化解决方法

C++和Python中递归实现计算斐波那契数列，当n=500时，两者都能正常计算，例如，

#include <iostream>
#include <array>
using namespace 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() {
    cout << fib(500)[0];
}

 但当n=5000，C++能正常计算，Python会报错：RecursionError: maximum recursion depth exceeded in comparison

但可以通过增加sys.setrecursionlimit(6000)，例如，

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(6000)
    print(fib(5000)[0])

然而，当n=50000，Python在我机器上崩溃了，而C++几毫秒得出结果151 。对于斐波那契数列，解决方案是用迭代代替递归。但其它递归问题可能就不这么容易了。下面在看一下问题原因及解决办法。

问题原因：

Python 对递归函数调用的数量有内部限制。该限制是可配置的，但是，函数链太深会导致堆栈溢出。这种潜在的限制¹适用于 C++ 和 Python。此限制也适用于所有函数调用，而不仅仅是递归调用。潜在的限制是执行堆栈大小。默认大小因系统而异，不同的函数调用消耗不同的内存量，因此限制不是指定为调用次数，而是以字节为单位。这在某些系统上也是可配置的。由于便携性问题，通常不建议修改该限制。C++对递归调用深度没有限制，除了栈的大小。作为一种完全编译的语言，循环（包括递归）在 C++ 中比在 Python 中快得多。

解决方法：

将递归函数转换为一个可以跟踪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])