Python递归限制与堆栈大小? [英] Python recursion limit vs stack size?

问题描述

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

I understand how in recursion every recursive call stacks on the stack; if the stack limit is exceeded, you get a stack overflow. Why then does Python's sys.getrecursionlimit() return a number; a max depth of recursive calls?

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

Does it not depend on what I do in that recursive function? Or does it somehow save the variables somewhere else, other than the stack? How does it work?

推荐答案

考虑这个问题的简单方法是:Python 堆栈实际上并不是一个连接所有帧的巨大数组，而是一个链接列表框架.¹ 但是，如果您使用 C 术语进行思考，即使这样也可能会产生误导.你似乎是:

The easy, if oversimplified, way to think about this is that the Python stack is not actually a giant array with all the frames concatenated, but a linked list of frames.¹ But even that can be misleading if you're thinking in, say, C terms. Which you seem to be:

或者它是否以某种方式将变量保存在堆栈之外的其他地方?

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

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

It does—in CPython, local variables² are stored in an array on the heap-allocated frame object—but that usually isn't the relevant question.

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

In C, a variable is a typed memory location. When you write int lst[100];, that allocates 400 bytes on the stack and names it lst.

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

In Python, a variable is just a name (in some namespace) for a value. Memory locations (and types) are a property of values, not variables, and they always live somewhere in the heap.³ Variables are just references to them. So, if you write lst = [0]*100, that's just 8 bytes for the variable (pointer) in the locals array, and then 864 bytes for the list object on the heap.⁴

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

The RecursionError limit is there because most Python code that goes to a depth of 1000 is probably going to just take a very long time allocate a whole bunch of Python frames before failing on either a MemoryError or a stack overflow segfault, so it's better to stop you before allocating all that memory and burning all that CPU.

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

More importantly, as tdelaney points out in a comment, recovering from either of those conditions is very difficult in Python—but recovering from a RecursionError is pretty simple; it unwraps the stack to the top of the recursion for you and leaves you in a predictable state.

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

But that rule of thumb doesn't apply to every program, just most of them—so if you know you have an algorithm that may go a few thousand frames deep without any problems, Python lets you increase the limit to, say, 10000 instead of 1000.

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

_{1. This is oversimplified because (at least in CPython) the interpreter is often actually chaining up calls on the C stack—but it's still useful to remember that there's a new frame object (and the other stuff the frame allocates) being heap allocated every time you recurse in Python, whether the interpreter is recursing or not. (Especially since Python is defined as never doing tail call elimination at the Python level, even if the interpreter actually does so in the eval loop.)}

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

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

_{3. And of course that "somewhere" is unspecified—Python is garbage-collected, whether using automatic refcounting plus a cycle detector as in CPython, or whatever the underlying JVM uses as in Jython. But in CPython, there's also a defined C API, where objects are C pointers to structs—and you can see the value of this pointer with the id function.}

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

_{4. Also, that 864 bytes is mostly just a list of 100 pointers to a single immutable 0 object, unlike C, where there are 100 separate mutable int slots that all have the value 0 in them.}

这篇关于Python递归限制与堆栈大小?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！