为什么 Python 递归如此昂贵，我们能做些什么呢？
Why is Python recursion so expensive and what can we do about it?
假设我们要计算一些斐波那契数，模 997。
对于 C++ 中的 n=500 我们可以 运行
#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 C++ 在几毫秒内找到答案 151 而 Python 崩溃（至少在我的机器上）。
为什么递归调用在 C++ 中如此便宜？我们能否以某种方式修改 Python 编译器，使其更容易接受递归？
当然，一种解决方案是用迭代代替递归。对于斐波那契数列，这很容易做到。然而，这将交换初始条件和终止条件，而后者对于许多问题来说是棘手的（例如 alpha–beta p运行ing）。所以一般来说，这需要程序员付出很多努力。
您可以使用以下方式增加递归限制：
import sys
sys.setrecursionlimit(new_limit)
但请注意，此限制的存在是有原因的，并且纯 Python 并未针对递归（以及一般的计算密集型任务）进行优化。
问题是 Python 对递归函数调用的次数有内部限制。
该限制是可配置的，如 Quentin Coumes' answer 所示。但是，函数链太深会导致堆栈溢出。此潜在限制¹ 适用于 C++ 和 Python。此限制也适用于所有函数调用，而不仅仅是递归调用。
总的来说：您不应该编写具有线性复杂度或更差的递归深度增长的²算法。对数递归通常很好。尾递归函数很容易重写为迭代。其他递归可以使用外部数据结构（通常是动态堆栈）转换为迭代。
一个相关的经验法则是，您不应该拥有自动存储的大型对象。这是特定于 C++ 的，因为 Python 没有自动存储的概念。
¹ 潜在的限制是执行堆栈大小。默认大小因系统而异，不同的函数调用消耗不同的内存量，因此限制不是指定为调用次数，而是以字节为单位。这在某些系统上也是可配置的。由于可移植性问题，我通常不建议触及该限制。
² 此经验法则的例外是某些保证尾递归消除的函数式语言 - 例如 Haskell - 在递归保证被消除的情况下可以放宽该规则。 Python 不是这样的语言，所讨论的函数不是尾递归的。虽然 C++ 编译器可以执行消除作为优化，但不能保证，并且通常不会在调试版本中进行优化。因此，该异常通常也不适用于 C++。
免责声明：以下是我的假设；我实际上并不知道他们的理由：Python 限制可能是一个检测潜在无限递归的功能，防止可能不安全的堆栈溢出崩溃并替换更受控制的 RecursionError.
Why are recursive calls so much cheaper in C++?
C++ 是一种编译语言。 Python 被解释。 （几乎）在 C++ 中一切都更便宜，除了从源代码到可执行程序的转换。
让我先回答你的直接问题：
Why are recursive calls so much cheaper in C++?
因为C++对递归调用深度没有限制，除了栈的大小。作为一种完全编译的语言，循环（包括递归）在 C++ 中比在 Python 中快得多（这就是像 numpy/scipy 这样的特殊 Python 模块直接使用 C 例程的原因）。此外，大多数 C++ 实现使用称为 尾递归消除 的特殊功能（请参阅本 post 后面部分）并将一些递归代码优化为迭代等价物。这在这里很好，但标准不保证，因此其他编译可能会导致程序严重崩溃 - 但尾递归可能不涉及这里。
如果递归太深并耗尽可用堆栈，您将调用众所周知的未定义行为，任何事情都可能发生，从立即崩溃到程序出错结果（恕我直言，后者更糟糕，无法检测到...）
Can we somehow modify the Python compiler to make it more receptive to recursion?
没有。 Python 实现明确地从不使用尾递归消除。您可以增加递归限制，但这几乎总是一个坏主意（请参阅稍后的 post 为什么）。
现在真正解释基本原理。
深度递归是邪恶的，句号。你不应该使用它。递归是一个方便的工具当你可以确保深度将保持在合理的范围内。 Python 使用 soft 限制来警告程序员在系统崩溃之前出现了错误。另一方面，优化 C 和 C++ 编译器通常会在内部将 tail recursion 更改为迭代循环。但是依赖它是非常危险的，因为微小的改变可能会阻止优化并导致应用程序崩溃。
正如在此 other SO post 中所发现的，常见的 Python 实现不实现 尾递归消除 。所以你不应该在 5000 深度使用递归，而是使用迭代算法。
由于您的基础计算需要所有斐波那契数直到指定数，因此迭代计算它们并不难。而且效率会高很多！
一个解决方案是一个蹦床：递归函数，而不是调用另一个函数，returns一个使用适当参数进行调用的函数。有一个更高级别的循环，它在一个循环中调用所有这些函数，直到我们得到最终结果。我可能没有很好地解释它；您可以在线找到做得更好的资源。
关键是这将递归转换为迭代。我不认为这会更快，甚至可能更慢，但递归深度仍然很低。
一个实现可能如下所示。为了清楚起见，我将 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])
“两者都能毫无问题地找到答案 996”
我确实看到至少一个问题：答案应该是 836，而不是 996。
您的两个函数似乎都计算 Fibonacci(2*n) % p，而不是 Fibonacci(n) % p。
996 是 Fibonacci(1000) % 997.
的结果
选择更高效的算法
低效算法始终是低效算法，无论它是用 C++ 还是 Python 编写的。
为了计算大的斐波那契数，有比使用 O(n) 调用的简单递归更快的方法（参见相关 article）。
对于大 n，这个递归 O(log n) Python 函数应该 运行 在你上面的 C++ 代码周围的圆圈中：
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci(n, p):
"Calculate Fibonacci(n) modulo p"
if n < 3:
return [0, 1, 1][n]
if n % 2 == 0:
m = n // 2
v1 = fibonacci(m - 1, p)
v2 = fibonacci(m, p)
return (2*v1 + v2) * v2 % p
else:
m = (n + 1) // 2
v1 = fibonacci(m, p) ** 2
v2 = fibonacci(m - 1, p) ** 2
return (v1 + v2) % p
print(fibonacci(500, 997))
#=> 836
print(fibonacci(1000, 997))
#=> 996
它会愉快地计算fibonacci(10_000_000_000_000_000, 997)。
可以添加递归级别作为参数，以查看递归需要进行多深，并以缩进显示。这是 n=500:
的示例
# Recursion tree:
500
249
124
61
30
14
6
2
3
1
2
7
4
15
8
31
16
62
125
63
32
250
您的示例看起来就像很长的对角线：
500
499
498
...
...
1
对于Windows 可执行文件，堆栈大小在可执行文件的header 中指定。对于 Python 3.7 x64 的 Windows 版本，该大小为 0x1E8480 或正好 2.000.000 字节。
该版本崩溃
Process finished with exit code -1073741571 (0xC00000FD)
如果我们 look that up 我们发现它是堆栈溢出。
我们可以在（本机）堆栈上使用像 WinDbg 这样的本机调试器（启用 child 进程调试）看到的是
[...]
fa 000000e9`6da1b680 00007fff`fb698a6e python37!PyArg_UnpackStack+0x371
fb 000000e9`6da1b740 00007fff`fb68b841 python37!PyEval_EvalFrameDefault+0x73e
fc 000000e9`6da1b980 00007fff`fb698a6e python37!PyArg_UnpackStack+0x371
fd 000000e9`6da1ba40 00007fff`fb68b841 python37!PyEval_EvalFrameDefault+0x73e
fe 000000e9`6da1bc80 00007fff`fb698a6e python37!PyArg_UnpackStack+0x371
ff 000000e9`6da1bd40 00007fff`fb68b841 python37!PyEval_EvalFrameDefault+0x73e
2:011> ? 000000e9`6da1bd40 - 000000e9`6da1ba40
Evaluate expression: 768 = 00000000`00000300
因此 Python 每次方法调用将使用 2 个堆栈帧，并且堆栈位置存在 768 字节的巨大差异。
如果您使用十六进制编辑器修改 EXE 中的值（制作备份副本），假设为 256 MB
你可以运行下面的代码
[...]
if __name__=='__main__':
sys.setrecursionlimit(60000)
print(fib(50000)[0])
它会给出 151 作为答案。
在 C++ 中，我们还可以强制堆栈溢出，例如通过传递 500.000 作为参数。调试时，我们得到
0:000> .exr -1
ExceptionAddress: 00961015 (RecursionCpp!fib+0x00000015)
ExceptionCode: c00000fd (Stack overflow)
[...]
0:000> k
[...]
fc 00604f90 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7]
fd 00604fb0 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7]
fe 00604fd0 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7]
ff 00604ff0 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7]
0:000> ? 00604ff0 - 00604fd0
Evaluate expression: 32 = 00000020
每个方法调用只有 1 个堆栈帧，堆栈上只有 32 个字节的差异。与 Python 相比，对于相同的堆栈大小，C++ 可以执行 768/32 = 24 倍以上的递归。
我的 Microsoft 编译器创建了默认堆栈大小为 1 MB 的可执行文件（发布版本，32 位）：
64 位版本与 64 位（也是发布版本）的堆栈差异。
使用的工具：
- Microsoft WinDbg Preview（免费）
- Sweetscape 010 Editor（商业）用 PE 文件模板
蹦床的替代方法是使用 reduce。
如果你可以把递归函数改成尾递归，你可以用reduce来实现，这里有一个可能的实现。
reduce 是在内部迭代实现的，因此您可以在不破坏堆栈的情况下使用递归函数。
def inner_fib(acc, num):
# acc is a list of two values
return [(acc[0]+acc[1]) % 997, (acc[0]+2*acc[1]) % 997]
def fib(n):
return reduce(inner_fib,
range(2, n+1), # start from 2 since n=1 is covered in the base case
[1,2]) # [1,2] is the base case
假设我们要计算一些斐波那契数，模 997。
对于 C++ 中的 n=500 我们可以 运行
#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 C++ 在几毫秒内找到答案 151 而 Python 崩溃（至少在我的机器上）。
为什么递归调用在 C++ 中如此便宜？我们能否以某种方式修改 Python 编译器，使其更容易接受递归？
当然，一种解决方案是用迭代代替递归。对于斐波那契数列，这很容易做到。然而，这将交换初始条件和终止条件，而后者对于许多问题来说是棘手的（例如 alpha–beta p运行ing）。所以一般来说，这需要程序员付出很多努力。
您可以使用以下方式增加递归限制：
import sys
sys.setrecursionlimit(new_limit)
但请注意，此限制的存在是有原因的，并且纯 Python 并未针对递归（以及一般的计算密集型任务）进行优化。
问题是 Python 对递归函数调用的次数有内部限制。
该限制是可配置的，如 Quentin Coumes' answer 所示。但是，函数链太深会导致堆栈溢出。此潜在限制¹ 适用于 C++ 和 Python。此限制也适用于所有函数调用，而不仅仅是递归调用。
总的来说：您不应该编写具有线性复杂度或更差的递归深度增长的²算法。对数递归通常很好。尾递归函数很容易重写为迭代。其他递归可以使用外部数据结构（通常是动态堆栈）转换为迭代。
一个相关的经验法则是，您不应该拥有自动存储的大型对象。这是特定于 C++ 的，因为 Python 没有自动存储的概念。
¹ 潜在的限制是执行堆栈大小。默认大小因系统而异，不同的函数调用消耗不同的内存量，因此限制不是指定为调用次数，而是以字节为单位。这在某些系统上也是可配置的。由于可移植性问题，我通常不建议触及该限制。
² 此经验法则的例外是某些保证尾递归消除的函数式语言 - 例如 Haskell - 在递归保证被消除的情况下可以放宽该规则。 Python 不是这样的语言，所讨论的函数不是尾递归的。虽然 C++ 编译器可以执行消除作为优化，但不能保证，并且通常不会在调试版本中进行优化。因此，该异常通常也不适用于 C++。
免责声明：以下是我的假设；我实际上并不知道他们的理由：Python 限制可能是一个检测潜在无限递归的功能，防止可能不安全的堆栈溢出崩溃并替换更受控制的 RecursionError.
Why are recursive calls so much cheaper in C++?
C++ 是一种编译语言。 Python 被解释。 （几乎）在 C++ 中一切都更便宜，除了从源代码到可执行程序的转换。
让我先回答你的直接问题：
Why are recursive calls so much cheaper in C++?
因为C++对递归调用深度没有限制，除了栈的大小。作为一种完全编译的语言，循环（包括递归）在 C++ 中比在 Python 中快得多（这就是像 numpy/scipy 这样的特殊 Python 模块直接使用 C 例程的原因）。此外，大多数 C++ 实现使用称为 尾递归消除 的特殊功能（请参阅本 post 后面部分）并将一些递归代码优化为迭代等价物。这在这里很好，但标准不保证，因此其他编译可能会导致程序严重崩溃 - 但尾递归可能不涉及这里。
如果递归太深并耗尽可用堆栈，您将调用众所周知的未定义行为，任何事情都可能发生，从立即崩溃到程序出错结果（恕我直言，后者更糟糕，无法检测到...）
Can we somehow modify the Python compiler to make it more receptive to recursion?
没有。 Python 实现明确地从不使用尾递归消除。您可以增加递归限制，但这几乎总是一个坏主意（请参阅稍后的 post 为什么）。
现在真正解释基本原理。
深度递归是邪恶的，句号。你不应该使用它。递归是一个方便的工具当你可以确保深度将保持在合理的范围内。 Python 使用 soft 限制来警告程序员在系统崩溃之前出现了错误。另一方面，优化 C 和 C++ 编译器通常会在内部将 tail recursion 更改为迭代循环。但是依赖它是非常危险的，因为微小的改变可能会阻止优化并导致应用程序崩溃。
正如在此 other SO post 中所发现的，常见的 Python 实现不实现 尾递归消除 。所以你不应该在 5000 深度使用递归，而是使用迭代算法。
由于您的基础计算需要所有斐波那契数直到指定数，因此迭代计算它们并不难。而且效率会高很多！
一个解决方案是一个蹦床：递归函数，而不是调用另一个函数，returns一个使用适当参数进行调用的函数。有一个更高级别的循环，它在一个循环中调用所有这些函数，直到我们得到最终结果。我可能没有很好地解释它；您可以在线找到做得更好的资源。
关键是这将递归转换为迭代。我不认为这会更快，甚至可能更慢，但递归深度仍然很低。
一个实现可能如下所示。为了清楚起见，我将 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])
“两者都能毫无问题地找到答案 996”
我确实看到至少一个问题：答案应该是 836，而不是 996。
您的两个函数似乎都计算 Fibonacci(2*n) % p，而不是 Fibonacci(n) % p。
996 是 Fibonacci(1000) % 997.
选择更高效的算法
低效算法始终是低效算法，无论它是用 C++ 还是 Python 编写的。
为了计算大的斐波那契数，有比使用 O(n) 调用的简单递归更快的方法（参见相关 article）。
对于大 n，这个递归 O(log n) Python 函数应该 运行 在你上面的 C++ 代码周围的圆圈中：
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci(n, p):
"Calculate Fibonacci(n) modulo p"
if n < 3:
return [0, 1, 1][n]
if n % 2 == 0:
m = n // 2
v1 = fibonacci(m - 1, p)
v2 = fibonacci(m, p)
return (2*v1 + v2) * v2 % p
else:
m = (n + 1) // 2
v1 = fibonacci(m, p) ** 2
v2 = fibonacci(m - 1, p) ** 2
return (v1 + v2) % p
print(fibonacci(500, 997))
#=> 836
print(fibonacci(1000, 997))
#=> 996
它会愉快地计算fibonacci(10_000_000_000_000_000, 997)。
可以添加递归级别作为参数，以查看递归需要进行多深，并以缩进显示。这是 n=500:
# Recursion tree:
500
249
124
61
30
14
6
2
3
1
2
7
4
15
8
31
16
62
125
63
32
250
您的示例看起来就像很长的对角线：
500
499
498
...
...
1
对于Windows 可执行文件，堆栈大小在可执行文件的header 中指定。对于 Python 3.7 x64 的 Windows 版本，该大小为 0x1E8480 或正好 2.000.000 字节。
该版本崩溃
Process finished with exit code -1073741571 (0xC00000FD)
如果我们 look that up 我们发现它是堆栈溢出。
我们可以在（本机）堆栈上使用像 WinDbg 这样的本机调试器（启用 child 进程调试）看到的是
[...]
fa 000000e9`6da1b680 00007fff`fb698a6e python37!PyArg_UnpackStack+0x371
fb 000000e9`6da1b740 00007fff`fb68b841 python37!PyEval_EvalFrameDefault+0x73e
fc 000000e9`6da1b980 00007fff`fb698a6e python37!PyArg_UnpackStack+0x371
fd 000000e9`6da1ba40 00007fff`fb68b841 python37!PyEval_EvalFrameDefault+0x73e
fe 000000e9`6da1bc80 00007fff`fb698a6e python37!PyArg_UnpackStack+0x371
ff 000000e9`6da1bd40 00007fff`fb68b841 python37!PyEval_EvalFrameDefault+0x73e
2:011> ? 000000e9`6da1bd40 - 000000e9`6da1ba40
Evaluate expression: 768 = 00000000`00000300
因此 Python 每次方法调用将使用 2 个堆栈帧，并且堆栈位置存在 768 字节的巨大差异。
如果您使用十六进制编辑器修改 EXE 中的值（制作备份副本），假设为 256 MB
你可以运行下面的代码
[...]
if __name__=='__main__':
sys.setrecursionlimit(60000)
print(fib(50000)[0])
它会给出 151 作为答案。
在 C++ 中，我们还可以强制堆栈溢出，例如通过传递 500.000 作为参数。调试时，我们得到
0:000> .exr -1
ExceptionAddress: 00961015 (RecursionCpp!fib+0x00000015)
ExceptionCode: c00000fd (Stack overflow)
[...]
0:000> k
[...]
fc 00604f90 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7]
fd 00604fb0 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7]
fe 00604fd0 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7]
ff 00604ff0 00961045 RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7]
0:000> ? 00604ff0 - 00604fd0
Evaluate expression: 32 = 00000020
每个方法调用只有 1 个堆栈帧，堆栈上只有 32 个字节的差异。与 Python 相比，对于相同的堆栈大小，C++ 可以执行 768/32 = 24 倍以上的递归。
我的 Microsoft 编译器创建了默认堆栈大小为 1 MB 的可执行文件（发布版本，32 位）：
64 位版本与 64 位（也是发布版本）的堆栈差异。
使用的工具：
- Microsoft WinDbg Preview（免费）
- Sweetscape 010 Editor（商业）用 PE 文件模板
蹦床的替代方法是使用 reduce。
如果你可以把递归函数改成尾递归，你可以用reduce来实现，这里有一个可能的实现。
reduce 是在内部迭代实现的，因此您可以在不破坏堆栈的情况下使用递归函数。
def inner_fib(acc, num):
# acc is a list of two values
return [(acc[0]+acc[1]) % 997, (acc[0]+2*acc[1]) % 997]
def fib(n):
return reduce(inner_fib,
range(2, n+1), # start from 2 since n=1 is covered in the base case
[1,2]) # [1,2] is the base case