为什么Python有最大递归深度？

Question

Python有一个最大递归深度，但没有最大迭代深度。为什么要限制递归？把递归看做迭代并不会更自然吗？而且不会限制递归调用次数。

让我简单地说一下，这个问题的根源来自于试图实现流（参见此问题了解更多关于流的细节）。例如，假设我们想编写一个流以产生自然数：

def stream_accum(s, n): # force the stream to a list of length n
    def loop(s, acc):
        if len(acc) == n:
            return acc
        hd, tl = s()
        return loop(tl, acc + [hd])
    return loop(s, [])


def nats():
    def loop(n):
        return n, lambda: loop(n+1)
    return loop(1)

流的递归定义非常吸引人。然而，我认为更好/更符合Python风格的方法是使用生成器。

- rookie

---

“有吸引力”的递归解决方案有许多不吸引人的方面。首先，它具有O(n**2)的行为，因为您不断地构建新列表来扩展它们。其次，考虑到您可以简单地迭代以生成自然数，它过于复杂。这是将Python编写成Scheme或Haskell的示例。不同的语言擅长不同的事情。使用迭代。 - Ned Batchelder

Answer 1

这里实际上存在几个问题。

首先，正如NPE的回答所解释的那样，Python没有消除尾调用，因此许多在Scheme中允许无限递归的函数在Python中受到限制。

其次，正如NPE再次解释的那样，无法消除的调用会占用调用堆栈中的空间。而即使在进行TCE的语言中，仍有很多递归函数无法像迭代一样处理。（考虑递归调用自身两次的简单斐波那契函数。）

但是为什么调用堆栈首先是有限的资源？Python栈帧至少在原则上可以在堆上实现并链接在一起（请参见Stackless以证明该原理的存在），而在64位内存空间中，有足够的空间容纳远远超过1000个栈帧。（实际上，在几乎任何现代平台上，甚至C堆栈都可以容纳远远超过1000个递归Python解释器调用。）

部分原因是历史性的：股票Python解释器使用固定的C堆栈在进行递归调用时调用自身，而它最初是为32位（甚至24位或20位）平台设计的，其中C堆栈非常小。

但这可以被更改，而Python 3.0将是更改的完美时机。那他们为什么没做呢？因为他们做出了有意识的语言设计决策。在Pythonic代码中，递归通常非常浅（例如遍历浅树结构的os.walk之类的代码）；如果您的函数达到接近1000的深度，则更可能是错误而不是故意的。因此，限制保持不变。当然，这有点循环——如果他们删除了限制（特别是如果他们消除了尾调用），更深的递归将变得更加惯用。但这就是重点：Guido不希望深度递归成为惯用语言。（大多数Python社区都同意。）

- abarnert

---

你可以通过调用 sys.setrecursionlimit 来增加 Python 调用栈的最大深度。 - Mayou36

Answer 2

这并不是 Python 独有的问题，而与每次调用在调用堆栈上占用空间以及堆栈大小有关。

仅迭代不消耗堆栈空间，因此不受此限制。

并非每个递归调用都需要消耗堆栈空间。例如，某些语言可以自动将尾递归转换为迭代。然而，CPython 不这样做（Python 优化尾递归吗？）。

您可以通过调用sys.setrecursionlimit来增加 Python 调用堆栈的最大深度。

- NPE

---

栈的大小并没有真正限制（除了堆有限制之外）。Python选择有意限制它。 - abarnert

Answer 3

递归需要在有限的调用堆栈上占用空间。使用过多层递归的代码会导致堆栈溢出错误（也因某个不知名网站而闻名）。Python似乎将此限制（有点武断）为大约1000个级别，但可以通过设置sys.setrecursionlimit增加。

迭代使用类似于for循环的东西，通过递增某些计数器并有条件地将指令指针设置回循环开头来实现。这在内存中是恒定的。

- Bas Swinckels