Python递归限制与堆栈大小？

Question

我明白了在递归中，每个递归调用是如何堆栈在堆栈上的；如果超过堆栈限制，则会出现堆栈溢出。那么为什么Python的sys.getRecursionLimit()返回一个数字；递归调用的最大深度？

这不是取决于我在递归函数中做了什么吗？还是以某种方式将变量保存在堆栈以外的其他地方？它是如何工作的？

Answer 1

考虑这个问题的一个简单方法是，Python堆栈实际上并不是一个连接所有帧的巨大数组，而是一个帧的链表。¹但如果你用C语言来思考，即使这样也会产生误导。你好像是：

还是以某种方式将变量保存在堆栈以外的其他地方？

确实如此--在CPython中，局部变量²存储在堆分配的frame对象上的数组中--但这通常不是相关的问题。

之所以存在recursionerror限制，是因为大多数深度为1000的Python代码在memoryerror或堆栈溢出segfault失败之前可能需要很长时间分配一整串Python帧，因此最好在分配所有内存和烧录所有CPU之前停止。

更重要的是，正如tdelaney在一篇评论中指出的那样，在Python中从这两种情况中的任何一种恢复都是非常困难的--但是从recursionerr恢复非常简单；它为您将堆栈展开到递归的顶部，并使您处于可预测的状态。

但这一经验法则并不适用于每一个程序，只适用于大多数程序--所以如果你知道你有一个算法可以在没有任何问题的情况下达到几千帧深度，Python允许你将极限提高到，比方说10000而不是1000。

_{1。这是过于简化的，因为（至少在CPython中）解释器实际上经常链接C堆栈上的调用--但记住在Python中每次递归时堆分配一个新的frame对象（以及frame分配的其他东西）仍然是有用的，无论解释器是否递归。（特别是因为Python被定义为从不在Python级别执行尾部调用消除，即使解释器实际上在eval循环中这样做。）}

_{2。从技术上讲，在Python中，所有变量都存储在一个名称空间中，这是一个从名称到对值的引用的映射。但CPython通过存储指针数组，然后让编译器将局部引用转换为数组查找而不是映射查找来优化局部变量。}

_{3。当然，“某处”是未指定的--Python是垃圾收集的，无论是像CPython那样使用自动refcounting加循环检测器，还是像Jython那样使用任何底层JVM。但在CPython中，还有一个定义的C API，其中对象是指向结构的C指针--您可以通过id函数看到这个指针的值。}

_{4。此外，864字节主要是指向单个不可变0对象的100个指针的列表，而不像C语言，后者有100个单独的可变int槽，其中都包含值0。}