为什么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)

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

Answer 1

实际上这里有一些问题。

首先，正如NPE的回答很好地说明的那样，Python不会消除尾部调用，因此许多允许进行无限递归的函数（例如Scheme）在Python中受到限制。

其次，正如NPE所解释的那样，无法消除的调用占用了调用堆栈上的空间。而且，即使在执行TCE的语言中，也有很多递归函数不能像迭代那样对待。（考虑一下朴素的Fibonacci函数，该函数递归调用两次。）

但是为什么调用栈首先是有限的资源呢？Python堆栈框架至少可以原则上在堆上实现并链接在一起（有关该原理的存在性证明，请参见Stackless），并且在64位内存空间中，可以容纳1000个以上的堆栈框架。（实际上，即使是几乎任何现代平台上的C堆栈，也都可以容纳1000多个递归Python解释器调用。）

部分原因是历史原因：当您进行递归调用时，现有的Python解释器使用固定的C堆栈来递归调用自身，它最初是为32位（甚至24位或20位）平台设计的，堆栈很小。

但这可能已经改变，Python
3.0将是更改它的理想场所。那么，为什么不呢？因为他们做出了自觉的语言设计决策。在Pythonic代码中，递归通常非常浅（例如，类似的代码os.walk会遍历浅树结构）。如果函数的深度达到1000左右，那么它很有可能是错误而不是有意的。因此，限制仍然存在。当然，这有点循环-
如果他们删除了限制（尤其是如果他们消除了尾部调用），则更深层次的递归将变得更加惯用。但这就是重点-
圭多（Guido）不需要一种习惯于深度递归的语言。（并且大多数Python社区都同意。）