为什么 Python 有最大递归深度? [英] Why does Python have a maximum recursion depth?

问题描述

Python 有最大递归深度，但没有最大迭代深度.为什么递归受到限制?像迭代一样对待递归，而不限制递归调用的次数不是更自然吗?

Python has a maximum recursion depth, but no maximum iteration depth. Why is recursion restricted? Wouldn't it be more natural to treat recursion like iteration, and not restrict the number of recursive calls?

我只想说这个问题的根源来自试图实现一个流(见这个问题 有关流的更多详细信息).例如，假设我们要编写一个流来生成自然数:

Let me just say that the source of this issue came from trying to implement a stream (see this question for more details about streams). For example, say we want to write a stream to produce the natural numbers:

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)

流的递归定义非常吸引人.但是，我想更好/更 Pythonic 的方法是使用生成器.

The recursive definition of streams is quite appealing. However, I guess the better/more pythonic approach would be to use generators.

推荐答案

这里其实有几个问题.

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

First, as NPE's answer nicely explains, Python doesn't eliminate tail calls, so many functions that would allow unlimited recursion in, say, Scheme are limited in Python.

其次，正如 NPE 所解释的那样，无法消除的调用会占用调用堆栈上的空间.而且，即使在执行 TCE 的语言中，也有很多递归函数不能被视为迭代.(考虑递归调用自己两次的朴素斐波那契函数.)

Second, as again as explained by NPE, calls that can't be eliminated take up space on the call stack. And, even in languages that do TCE, there are plenty of recursive functions that can't be treated like iteration. (Consider the naive Fibonacci function that recursively calls itself twice.)

但是为什么调用堆栈首先是一种有限资源?Python 堆栈帧至少原则上可以在堆上实现并链接在一起(参见 Stackless 的存在证明这个原则)，并且在 64 位内存空间中，有超过 1000 个堆栈帧的空间.(事实上​​，即使是几乎所有现代平台上的 C 堆栈也可以容纳超过 1000 个递归 Python 解释器调用.)

But why is the call stack a finite resource in the first place? Python stack frames can at least in principle be implemented on the heap and linked together (see Stackless for an existence proof of that principle), and in a 64-bit memory space, there's room for a whole lot more than 1000 stack frames. (In fact, even the C stack on almost any modern platform can hold a whole lot more than 1000 recursive Python interpreter calls.)

部分原因是历史原因:当您进行递归调用时，股票 Python 解释器使用固定的 C 堆栈来递归调用自身，并且它最初是为 32 位(甚至 24 位或 20 位)平台设计的C 堆栈非常小.

Part of the reason is historical: the stock Python interpreter uses the fixed C stack to call itself recursively whenever you make a recursive call, and it was originally designed for 32-bit (and even 24- or 20-bit) platforms where that C stack is pretty small.

但这本来可以改变的，而 Python 3.0 将是一个完美的改变它的地方.那么，他们为什么不呢?因为他们做出了有意识的语言设计决定.在 Pythonic 代码中，递归通常非常浅(例如，像 os.walk 这样的代码遍历浅树结构)；如果您的函数达到接近 1000 的任何深度，则更有可能是错误而不是故意的.所以，限制仍然存在.当然，这有点循环——如果他们取消限制(特别是如果他们消除尾调用)，更深层次的递归将变得更加惯用.但这就是重点——Guido 不想要一种深度递归是惯用的语言.(大多数 Python 社区都同意.)

But that could have been changed, and Python 3.0 would have been a perfect place to change it. So, why didn't they? Because they made a conscious language design decision. In Pythonic code, recursion is generally very shallow (e.g., code like os.walk that traverses shallow tree structures); if your function hits a depth of anywhere near 1000, it's more likely to be a bug than to be intentional. So, the limit stays. Of course this is a bit circular—if they removed the limit (and, especially, if they eliminated tail calls), deeper recursion would become more idiomatic. But that's kind of the point—Guido doesn't want a language where deep recursion is idiomatic. (And most of the Python community agrees.)

这篇关于为什么 Python 有最大递归深度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！