为什么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位)平台,其中C堆栈非常小.

但这可能已经改变了,Python 3.0将是一个改变它的完美场所.那么,他们为什么不呢？因为他们做出了有意识的语言设计决定.在Pythonic代码中,递归通常非常浅(例如,像os.walk遍历浅树结构的代码); 如果你的功能达到1000附近的任何深度,它更可能是一个错误,而不是故意的.所以,限制仍然存在.当然这有点循环 - 如果他们删除了限制(特别是,如果他们消除了尾部调用),更深层次的递归将变得更加惯用.但这就是重点 - 圭多并不想要一种语言,其中深度递归是惯用的.(并且大多数Python社区都同意.)

Answer 2

这不是Python独有的,并且与调用堆栈上的每个调用占用空间有关,并且堆栈的大小是有限的.

单独迭代不会占用堆栈空间,因此不受此限制.

并非每个递归调用都需要消耗堆栈空间.例如,某些语言可以自动将尾递归转换为迭代.但是,CPython选择不这样做(Python会优化尾递归吗？).

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

Answer 3

递归需要调用堆栈上的空间,其大小有限.使用过多级别递归的代码会产生一个称为堆栈溢出的错误(也被一些不起眼的网站所熟知).Python似乎将此(有点任意)限制在1000左右,但这可以通过设置来增加sys.setrecursionlimit.

迭代使用类似for-loop的东西,它通过递增一些计数器并有条件地将指令指针设置回循环的开头来实现.这在记忆中是不变的.