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

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

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

原文由 jtallk 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

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

原文由 Roel Schroeven 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

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

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

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

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

---

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

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

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

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

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

原文由 eerorika 发布，翻译遵循 CC BY-SA 4.0 许可协议