为什么 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=50000C++，当 Python 崩溃时（至少在我的机器上），它会在几毫秒内找到答案 151。

为什么递归调用在 C++ 中如此便宜？我们能否以某种方式修改 Python 编译器以使其更容易接受递归？

当然，一种解决方案是用迭代代替递归。对于斐波那契数列，这很容易做到。然而，这将交换初始条件和终止条件，后者对于许多问题（例如 alpha-beta 剪枝）来说很棘手。所以一般来说，这需要程序员付出很多努力。

Answer 1

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

该限制是可配置的，如Quentin Coumes 的回答所示。但是，函数链太深会导致堆栈溢出。这种潜在的限制¹适用于 C++ 和 Python。此限制也适用于所有函数调用，而不仅仅是递归调用。

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

一个相关的经验法则是，您不应该拥有具有自动存储功能的大型对象。这是特定于 C++ 的，因为 Python 没有自动存储的概念。

¹ 潜在的限制是执行堆栈大小。默认大小因系统而异，不同的函数调用消耗不同的内存量，因此限制不是指定为调用次数，而是以字节为单位。这在某些系统上也是可配置的。由于便携性问题，我通常不建议触及该限制。

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

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

为什么递归调用在 C++ 中如此便宜？

C++ 是一种编译语言。Python 被解释。（几乎）C++ 中的一切都更便宜，除了从源代码到可执行程序的翻译。

Answer 2

让我先回答你的直接问题：

为什么递归调用在 C++ 中如此便宜？

因为C++对递归调用深度没有限制，除了栈的大小。作为一种完全编译的语言，循环（包括递归）在 C++ 中比在 Python 中快得多（这就是为什么像 numpy/scipy 这样的特殊 Python 模块直接使用 C 例程的原因）。此外，大多数 C++ 实现使用称为尾递归消除的特殊功能（见本文后面部分）并将一些递归代码优化为迭代等价物。这在这里很好，但标准并不能保证，因此其他编译可能会导致程序崩溃 - 但这里可能不涉及尾递归。

如果递归太深并且耗尽了可用堆栈，您将调用众所周知的未定义行为，任何事情都可能发生，从立即崩溃到给出错误结果的程序（恕我直言，后者更糟糕，无法检测到...... )

我们能否以某种方式修改 Python 编译器以使其更容易接受递归？

不。Python 实现明确地从不使用尾递归消除。您可以增加递归限制，但这几乎总是一个坏主意（请参阅本文后面的原因）。

现在是对基本原理的真实解释。

深度递归是邪恶的，句号。你永远不应该使用它。当您可以确保深度保持在合理范围内时，递归是一个方便的工具。Python 使用软限制来警告程序员在系统崩溃之前出现问题。另一方面，优化 C 和 C++ 编译器通常在内部将尾递归更改为迭代循环。但是依赖它是非常危险的，因为轻微的更改可能会阻止优化并导致应用程序崩溃。

正如在其他 SO 帖子中发现的那样，常见的 Python 实现没有实现尾递归消除。所以你不应该使用 5000 深度的递归，而是使用迭代算法。

由于您的底层计算将需要指定的所有斐波那契数，因此迭代计算它们并不难。此外，它会更有效率！

Answer 3

一个解决方案是蹦床：递归函数不是调用另一个函数，而是返回一个函数，该函数使用适当的参数进行调用。有一个更高一级的循环在循环中调用所有这些函数，直到我们得到最终结果。我可能没有很好地解释它；您可以在网上找到做得更好的资源。

关键是这将递归转换为迭代。我不认为这更快，甚至可能更慢，但递归深度保持较低。

一个实现可能如下所示。为了清楚起见，我将这对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])

Answer 4

“两者都会毫无问题地找到答案 996”

我确实看到了至少一个问题：答案应该是836，而不是 996 。

似乎您的两个函数都计算Fibonacci(2*n) % p，而不是Fibonacci(n) % p。

996是 的结果Fibonacci(1000) % 997。

选择更有效的算法

一个低效的算法仍然是一个低效的算法，不管它是用 C++ 还是 Python 编写的。

为了计算大的斐波那契数，有比 O(n) 调用的简单递归更快的方法（参见相关文章）。

对于大 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

Answer 5

您可以使用以下方法增加递归限制：

import sys

sys.setrecursionlimit(new_limit)

但请注意，此限制存在是有原因的，并且纯 Python 并未针对递归（以及一般的计算密集型任务）进行优化。

Answer 6

对于 Windows 可执行文件，堆栈大小在可执行文件的标头中指定。对于 Python 3.7 x64 的 Windows 版本，该大小为 0x1E8480 或正好 2.000.000 字节。

该版本崩溃了

Process finished with exit code -1073741571 (0xC00000FD)

如果我们查看它，我们会发现它是一个 Stack Overflow。

我们可以在使用像 WinDbg 这样的本机调试器（启用子进程调试）的（本机）堆栈上看到的是

[...]
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 位（也是 Release 版本）。

使用的工具：

• Microsoft WinDbg 预览版（免费）
• Sweetscape 010 编辑器（商业版）带有 PE 文件模板