每个对象的最大递归深度是多少？

Question

我正在重构Python信号处理框架，因为我们遇到了一个最大重复深度错误。你知道吗

对这个错误最可能的解释是，有时单个类的大量实例是从类的itsinit方法递归创建的。实际上，模拟这种情况的实验会导致异常运行时错误：“超过了最大递归深度”。你知道吗

当我将创建链中的下一个元素转移到管理这些对象的容器时，问题似乎消失了，尽管我天真地理解了相同深度的调用堆栈。我通过所有先前创建的对象调用create。（参见示例代码）。你知道吗

我倾向于得出这样的结论：递归深度限制是以某种方式为每个对象（无论是类还是实例）设置的。当我们通过init递归创建时，可能会把所有的东西都放在类的堆栈上，就像我们通过同一类的一行实例递归创建它们一样，所有对象的递归深度都非常有限。你知道吗

我正在为这个假设寻求一些证实，但发现很难得到证实或反驳。你知道吗

import sys

class Chunk(object):
    pre=None
    post=None
    def __init__(self, container,pre):
        print 'Chunk Created'
        self.pre=pre
        self.container=container

    def create(self,x):
        if self.post == None:
            self.post=Chunk(self.container,self)
            newChunk =self.post
        else:
            newChunk =self.post.create(x+1)
        return newChunk

    def droprefs(self):
        print 'refcount droprefs start: ', sys.getrefcount(self)
        if not self.pre ==None:
            self.pre.droprefs()

        self.pre=None
        self.post=None
        self.container=None
        print 'refcount droprefs end: ', sys.getrefcount(self)

    def claimContainer(self):
        self.container.setmasterchunk(self)
        self.pre.droprefs()
        self.pre=None

class Container(object):
    masterchunk=None

    def __init__(self):
        self.masterchunk=Chunk(self, None)

    def setmasterchunk(self, chunk):
        print 'refcount 5: ', sys.getrefcount(self.masterchunk)
        self.masterchunk=chunk
        print 'refcount 6: ', sys.getrefcount(self.masterchunk)

    def testrecursion(self,n):

        for i in range(n):
            print 'refcount 6: ', sys.getrefcount(self.masterchunk)
            newChunk=self.masterchunk.create(1)

        return newChunk

    def testhistoryremoval(self,chunk):
        chunk.claimContainer()



if __name__ == '__main__':
    C=Container()
    middle=C.testrecursion(300)
    last=C.testrecursion(600)
    last=C.testhistoryremoval(middle)

    if middle== C.masterchunk:
        print 'SUCCESS'

添加注释：

显示最大递归深度的代码：

import sys
from time import sleep

class Chunk(object):
    pre=None
    post=None
    def __init__(self, container,pre,n):
        print 'Chunk Created'
        self.pre=pre
        self.container=container

        if n>0:
            self.post=Chunk(self.container,self,n-1)

    def droprefs(self):
        print 'refcount droprefs start: ', sys.getrefcount(self)
        if not self.pre ==None:
            self.pre.droprefs()

        self.pre=None
        self.post=None
        self.container=None
        print 'refcount droprefs end: ', sys.getrefcount(self)

    def claimContainer(self):
        self.container.setmasterchunk(self)
        self.pre.droprefs()
        self.pre=None

class Container(object):
    masterchunk=None

    def __init__(self):
        pass

    def setmasterchunk(self, chunk):
        print 'refcount 5: ', sys.getrefcount(self.masterchunk)
        self.masterchunk=chunk
        print 'refcount 6: ', sys.getrefcount(self.masterchunk)

    def testrecursion(self,n):
        self.masterchunk=Chunk(self,None,n)



if __name__ == '__main__':
    print('Try 10')
    C0=Container()
    C0.testrecursion(10)

    sleep(2)

    print('Try 1000')
    C1=Container()
    C1.testrecursion(1000)

Answer 1

不，这是一个全局递归深度。您描述的情况意味着，当您超过堆栈限制时，您将捕获异常并继续处理下一个对象。此过程删除相关的堆栈项，将递归分解到其起点。你知道吗

从下一个对象开始。如果这一个不超过堆栈深度，它将顺利完成之前的堆栈条目不影响新的一个。你知道吗

Answer 2

您可以将方法重写为迭代的而不是递归的。这避免了递归深度错误的可能性，无论数据结构变得有多深。你知道吗

create方法会变成这样：

def create(self, x): # the `x` arg is not actually used for anything?
    chunk = self

    while chunk.post is not None:
        chunk = chunk.post

    chunk.post = Chunk(self.container, chunk)

    return self.post # this matches the old code but you may actually want `return self.post`

你可以用droprefs做类似的事情。您当前的代码似乎从列表的末尾向前迭代，这可能是您想要的，也可能不是您想要的。下面是迭代行为的直接翻译：

def droprefs(self):
    chunk = self

    while chunk:
        next = chunk.pre # this iterates backwards, to go forwards use `next = chunk.post`

        chunk.pre = None
        chunk.post = None
        chunk.container = None

        chunk = next

我还要注意的是，除非您希望外部代码包含对早期Chunk的引用，否则您可能根本不需要使用droprefs。在claimContainer执行self.pre = None之后，垃圾收集器应该能够清理所有早期的Chunk实例，因为没有更多的外部引用。去掉它们之间的引用可能会使它工作得更快（因为pre和post属性形成引用循环），但这并不是严格必要的。你知道吗

Answer 3

在我使用的实现中，设置

sys.setrecursionlimit(907)

演示这是您达到的递归深度。你知道吗

---

对于您的问题，答案是否定的。在CPython的源代码中，您可以看到递归深度是每个线程，而不是每个对象。你知道吗

pystate.h：

typedef struct _ts {
    /* See Python/ceval.c for comments explaining most fields */

    //...
    int recursion_depth;
    //...
}

ceval.c：

/* the macro Py_EnterRecursiveCall() only calls _Py_CheckRecursiveCall()
   if the recursion_depth reaches _Py_CheckRecursionLimit.
   If USE_STACKCHECK, the macro decrements _Py_CheckRecursionLimit
   to guarantee that _Py_CheckRecursiveCall() is regularly called.
   Without USE_STACKCHECK, there is no need for this. */
int
_Py_CheckRecursiveCall(const char *where)
{
    PyThreadState *tstate = PyThreadState_GET();
    //...
    if (tstate->recursion_depth > recursion_limit) {
         tstate->recursion_depth;
        tstate->overflowed = 1;
        PyErr_Format(PyExc_RecursionError,
                     "maximum recursion depth exceeded%s",
                     where);
        return -1;
     }
   //...
}

tstate是线程状态的简写。你知道吗