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

Question

#include <iostream>
using namespace std;

pair<int, int> fib(int n){
    if(n==1) return pair<int, int>(1, 2);
    pair<int, int> x=fib(n-1);
    return pair<int, int>((x.first+x.second) % 997, (x.first+2*x.second) % 997);
}

int main(){
    cout << fib(500).first;
}

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没有问题。我们使用modulos来保持合理的输出大小，使用pair来避免指数分支。

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

Answer 1

问题是Python对递归函数调用的数量有一个内部限制。

这个限制是可配置的，如昆汀·库姆斯的答案所示。但是，过深的函数链会导致堆栈溢出。这个底层限制¹同时适用于C++和Python。这种限制也适用于所有函数调用，而不仅仅是递归调用。

一般来说：您不应该编写具有线性复杂度或更糟的递归深度增长的²算法。对数增长递归通常很好。尾递归函数作为迭代重写是很简单的。其他递归可以使用外部数据结构（通常是动态堆栈）转换为迭代。

¹基础限制是执行堆栈大小。默认大小在不同的系统中是不同的，不同的函数调用消耗不同的内存，因此限制不是以调用次数来指定的，而是以字节来指定的。这在某些系统上也是可配置的。由于可移植性方面的考虑，我通常不建议触及该限制。

²这个经验法则的例外是某些保证尾部递归消除的函数语言（如Haskell)，在保证消除的递归的情况下，该规则可以放松。Python不是这样一种语言，所讨论的函数也不是尾递归的。虽然C++编译器可以将消除作为一种优化来执行，但这并不保证，而且通常在调试构建中没有进行优化。因此，这个例外通常也不适用于C++。

免责声明：以下是我的假设，实际上我不知道它们的基本原理：Python限制可能是一个检测潜在无限递归的特性，防止可能不安全的堆栈溢出崩溃，并替换一个更受控制的recursionerr。

为什么在C++中递归调用要便宜得多？

C++是一种编译语言。对Python进行了解释。在C++中，几乎所有的东西都便宜，除了从源代码到可执行程序的翻译。