Python递归限制与堆栈大小？

Question

我理解在递归中每次递归调用都会堆叠在栈上；如果超过了栈限制，就会出现堆栈溢出。

那么Python的sys.getrecursionlimit()为什么会返回一个数字，即递归调用的最大深度呢？

它不是取决于我在递归函数中做了什么吗？还是说它会在其他地方保存变量，而不是栈上？它是如何工作的呢？

- gunta

---

极不可能从进程级堆栈溢出或内存不足的情况中恢复。 - tdelaney

你可能会发现这个链接有帮助：https://dev59.com/nmAg5IYBdhLWcg3wOotQ - PM 2Ring

@tdelaney 是的，这可能是最重要的一点：你几乎总是可以从RecursionError中恢复过来，但是你很少能够从将递归深度增加到荒谬程度导致的MemoryError中恢复过来... - abarnert

递归的“限制”实际上并不存在。请参考此答案以获取示例和解释。 - Mulan

Answer 1

简单来说，Python堆栈实际上不是一个将所有帧串联的巨大数组，而是帧的链表。但如果你以C的术语思考，即使这样也可能会产生误导。在CPython中，局部变量存储在堆分配的帧对象的数组中，但通常这不是相关的问题。在Python中，变量只是一个名称（在某个命名空间中）对应一个值。内存位置和类型是值的属性，不是变量的属性，它们总是存在于堆中。变量只是对它们的引用。因此，如果您写lst = [0]*100，则变量（指针）在本地数组中只占用8字节，而堆中的列表对象需要864字节。 RecursionError限制存在是因为大多数深度达到1000的Python代码可能只需要分配大量的Python帧就会花费很长时间，然后在MemoryError或栈溢出段错误失败，因此最好在分配所有那些内存和CPU之前停止它。更重要的是，正如tdelaney在评论中指出的那样，从其中任何一种情况恢复在Python中都非常困难，但从RecursionError中恢复相当简单；它会将堆栈解开至递归的顶部，并将您留在可预测的状态中。

但是这个经验法则并不适用于所有程序，仅适用于大多数程序 - 因此，如果您知道自己的算法可能会深入几千个帧而没有任何问题，Python允许您将限制增加到10000而不是1000。

---

_{1. 这个规则过于简单了，因为（至少在CPython中）解释器实际上经常在C栈上链接调用，但仍然有用的是要记住每次在Python中进行递归时都会分配一个新的 frame 对象（以及 frame 分配的其他内容），无论解释器是否正在递归。 (特别是因为 Python 被定义为在 Python 级别永远不会执行尾递归消除，即使解释器在 eval 循环中实际上进行了这样的操作。)}

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

_{3. 当然，“某处”是未指定的 - Python 是垃圾收集的，无论使用 CPYthon 中的自动引用计数加循环检测，还是 Jython 中底层 JVM 使用的任何方式。但在 CPython 中，也有一个定义的 C API，其中对象是指向结构体的 C 指针 - 您可以使用 id 函数查看此指针的值。}

_{4. 此外，这个 864 字节主要只是一个指向单个不可变的 0 对象的 100 个指针的列表，不像在 C 中，有 100 个分离的可变的 int 插槽，它们都具有值 0。}

- abarnert