Python递归限制与堆栈大小？

Question

我理解在递归中如何在堆栈上的每个递归调用堆栈; 如果超出堆栈限制,则会出现堆栈溢出.那么,为什么Python的getrecursionlimit()返回一个数字 - 最大深度的递归调用？它不依赖于我在递归函数中的作用吗？或者以某种方式将变量保存在除堆栈之外的其他位置？它是如何工作的？

Answer 1

最简单的,如果过于简单,方法来思考这是Python的堆栈实际上不是一个巨大的阵列连接在一起的所有帧,但是帧的链接列表.¹但是,如果你考虑C语言,那么即便如此也会产生误导.你似乎是:

或者以某种方式将变量保存在除堆栈之外的其他位置？

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

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

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

这个RecursionError限制是因为大多数深度为1000的Python代码可能需要花费很长时间来分配一大堆Python帧才会失败MemoryError或者堆栈溢出段错误,所以最好先阻止你分配所有内存并烧掉所有CPU.

更重要的是,正如tdelaney在评论中指出的那样,在Python中从这两种情况中恢复是非常困难的 - 但从a中恢复RecursionError非常简单; 它会将堆栈展开到递归的顶部,并使您处于可预测状态.

但是这个经验法则并不适用于每个程序,只是大多数程序 - 所以如果你知道你的算法可能会有几千帧而没有任何问题,那么Python允许你将限制增加到10000,而不是1000.

_{1.这是过于简单的,因为(至少在CPython中)解释器通常实际上是在C堆栈上链接调用 - 但是仍然有用的是记住有一个新的帧对象(以及帧分配的其他东西)是每个堆分配的你在Python中递归的时间,解释器是否正在递归.(特别是因为Python被定义为在Python级别从不进行尾调用消除,即使解释器实际上在eval循环中这样做了.)}

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

_{3.当然"某处"是未指定的 - 无论是使用自动引用计数加上CPython中的循环检测器,还是使用Jython中底层JVM使用的任何内容,Python都是垃圾收集的.但是在CPython中,还有一个已定义的C API,其中对象是指向结构的C指针 - 您可以使用该id函数查看此指针的值.}

_{4.此外,864字节大多只是一个指向单个不可变0对象的100个指针的列表,与C不同,其中有100个单独的可变int插槽,它们都具有值0.}