Python递归限制与堆栈大小？

Question

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

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

Answer 1

简单但过于简单的思考方式是，Python 堆栈实际上并不是所有帧连接在一起的巨大数组，而是帧的链接列表。¹ 但即使这样也可以如果你在思考，比如说，C 术语，那会产生误导。你似乎是这样的:

Or does it somehow save the variables somewhere else, other than the stack?

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

在 C 中，变量是类型化的内存位置。当您编写 int lst[100]; 时，它会在堆栈上分配 400 个字节并将其命名为 lst。

在 Python 中，变量只是一个值的名称(在某些命名空间中)。内存位置(和类型)是值的属性，而不是变量，它们总是位于堆中的某个位置。³ 变量只是对它们的引用。因此，如果您编写 lst = [0]*100，局部数组中的变量(指针)只有 8 个字节，堆上的列表对象有 864 个字节。 ⁴

---

存在 RecursionError 限制是因为 大多数 深度为 1000 的 Python 代码可能只需要很长时间来分配一大堆 Python 帧在因 MemoryError 或堆栈溢出段错误失败之前，最好在分配所有内存和消耗所有 CPU 之前停止您。

更重要的是，正如 tdelaney 在评论中指出的那样，在 Python 中从任何一种情况中恢复都非常困难——但是从 RecursionError 中恢复非常简单；它为您将堆栈解包到递归的顶部，让您处于可预测的状态。

但是这个经验法则并不适用于每个程序，只是大多数程序——所以如果你知道你有一个算法可以深入几千帧而没有任何问题，Python 让您将限制增加到例如 10000 而不是 1000。

---

<子>1。这过于简单化了，因为(至少在 CPython 中)解释器 通常实际上是在 C 堆栈上链接调用——但记住有一个新的框架对象(以及框架分配的其他内容)仍然很有用) 每次在 Python 中递归时都会分配堆，无论解释器是否递归。 (特别是因为 Python 被定义为从不在 Python 级别进行尾调用消除，即使解释器实际上在 eval 循环中这样做。)

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

<子>3。当然，“某处”是未指定的——Python 是垃圾收集的，无论是使用自动引用计数加上 CPython 中的循环检测器，还是 Jython 中使用的任何底层 JVM。但在 CPython 中，还有一个已定义的 C API，其中对象是指向结构的 C 指针——您可以使用 id 函数查看此指针的值。

<子>4。此外，这 864 个字节主要只是一个包含 100 个指向单个不可变 0 对象的指针的列表，这与 C 不同，C 中有 100 个单独的可变 int 槽，它们都具有值0 在其中。