为什么Python的递归操作如此昂贵，我们该如何处理它？
为什么Python的递归操作如此昂贵，我们该如何处理它？
假设我们想要计算Fibonacci数字，取模997。
对于C++中的n = 500，我们可以运行
#include
#include
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，C++在毫秒内找到答案151，而Python会崩溃（至少在我的机器上）。
为什么在C++中递归调用要便宜得多？我们是否可以以某种方式修改Python编译器，使其更接受递归？
当然，一种解决方案是用迭代替换递归。对于Fibonacci数字，这很容易做到。但是，这将交换初始和终端条件，后者对于许多问题（例如Alpha-Beta剪枝）是棘手的。因此，通常这需要程序员大量的努力。
首先回答您的直接问题：
为什么C++中递归调用会更加便宜？
因为C++在递归调用深度上没有限制，除了栈的大小。并且作为一种完全编译型语言，循环（包括递归）在C++中比在Python中更加快速（这也是为什么特殊的Python模块，如numpy/scipy，直接使用C语言程序的原因）。此外，大多数C++实现使用一种被称为尾递归消除的特殊功能（稍后在本文中解释），将一些递归代码优化为迭代等价形式。这很好，但不是标准保证的，因此其他编译可能导致程序崩溃严重——但在这里可能没有涉及尾递归。
如果递归深度太深，超出了可用的堆栈，您将调用众所周知的未定义行为，在这种情况下可以发生任何事情，从立即崩溃到程序给出错误结果（个人认为后者更糟糕，不能被检测到...）
我们是否可以通过修改Python编译器使其更容易接受递归？
不可以。Python实现显式地从不使用尾递归消除。您可以增加递归限制，但这几乎总是一个坏主意（稍后在本文中解释原因）。
现在对基本原理的真正解释。
深递归很危险，没有任何疑问。您不应该使用它。当您可以确保深度保持在正常限制范围内时，递归是一个方便的工具。Python使用一个软限制来警告程序员，在崩溃系统之前发现错误。另一方面，优化C和C++编译器经常在内部将尾递归转换为迭代循环。但依赖它是非常危险的，因为轻微的更改可能会阻止这种优化并导致应用程序崩溃。
正如在此其他SO帖子中发现的那样，常见的Python实现不实现尾递归消除。因此，您不应该在5000深度处使用递归，而应使用迭代算法。
由于您的底层计算将需要所有指定数字的斐波那契数，因此很容易通过迭代计算它们。此外，这将更加有效率！
问题在于Python对于递归函数调用次数有一个内部限制。如Quentin Coumes的回答中所示，该限制可以进行配置。然而，太深的函数链会导致堆栈溢出。这种潜在的限制¹在C++和Python中都适用，而且这种限制不仅适用于递归调用，也适用于所有函数调用。通常情况下，在算法设计时，不应编写²线性复杂度或更高复杂度的递归算法。对数级别的递归通常是没问题的。尾递归函数很容易重新写成迭代。其他的递归可以使用外部数据结构（通常是动态栈）转换为迭代。另外，一个相关的经验法则是，不应该有自动存储的大型对象。这是C++专属的，因为Python没有自动存储的概念。
¹ 这种潜在的限制是执行堆栈大小。默认大小因操作系统而异，不同的函数调用消耗的内存量也不同，因此该限制没有以调用次数的形式指定，而是以字节为单位指定。在某些系统上，该限制是可以进行配置的。我通常不建议触及限制，因为这涉及到可移植性问题。
² 以下是我的假设，我并不实际知道他们的原理：Python限制可能是为了检测潜在的无限递归，从而避免可能不安全的堆栈溢出崩溃，并替换为更可控的RecursionError。
为什么C++递归调用如此便宜？
C++是一种编译语言，而Python是解释语言。（几乎）所有的东西在C++中都比较便宜，除了从源代码到可执行程序的翻译。