python递归迭代超过树实现的限制 [英] python recursive iteration exceeding limit for tree implementation

问题描述

我正在 python 中动态实现一棵树.我定义了一个类如下

I'm implementing a tree dynamically in python. I have defined a class as below

class nodeobject():

    def __init__(self,presentnode=None,parent=None):
        self.currentNode = presentnode
        self.parentNode = parent
        self.childs = []

我有一个函数可以为池中的每个节点获取可能的子节点

I have a function which gets possible childs for every node from a pool

def findchildren(node, childs):` `# No need to write the whole function on how it gets childs

现在我有一个递归函数，它从头节点(没有父节点)开始，并为每个节点递归向下移动链(基本情况是最后一个没有子节点的节点)

Now I have a recursive function that starts with the head node (no parent) and moves down the chain recursively for every node (base case being the last node having no children)

def tree(dad,children):

    for child in children:
        childobject = nodeobject(child,dad)
        dad.childs.append(childobject)
        newchilds = findchildren(child, children)
        if len(newchilds) == 0:
            lastchild = nodeobject(newchilds,childobject)
            childobject.childs.append(lastchild)
            loopchild = copy.deepcopy(lastchild)
            while loopchild.parentNode != None:
                print "last child"
                result.append(loopchild.currentNode) # result global to store values
                loopchild = copy.deepcopy(loopchild.parentNode)
        else:
            tree(childobject,newchilds)

树的形成仅适用于一定数量的输入.一旦池变大，就会导致MAXIMUM RECURSION DEPTH EXCEEDED"

The tree formation works for certain number of inputs only. Once the pool gets bigger, it results into "MAXIMUM RECURSION DEPTH EXCEEDED"

我尝试使用 set.recursionlimit() 设置递归限制，但它不起作用.程序崩溃.我想实现一个递归堆栈，有人可以帮忙吗，我尝试了很长时间也没去哪里??另外，除了堆栈之外还有其他方法可以解决这个问题吗?

I have tried setting the recursion limit with set.recursionlimit() and it doesn't work. THe program crashes. I want to implement a stack for recursion, can someone please help, I have gone no where even after trying for a long time ?? Also, is there any other way to fix this other than stack ?

推荐答案

当您尝试更改递归深度时，您的程序可能会崩溃，因为您超出了系统堆栈大小强加的硬递归限制.设置 sys.recursionlimit() 只会让 Python 对深度不那么严格，但不会影响您的平台实际支持的内容.

When you try to change the recursion depth, your program probably crashes because you are exceeding the hard recursion limit imposed by the size of the stack on your system. Setting sys.recursionlimit() only makes Python less strict about the depth, but it doesn't affect what your platform will actually support.

Python 有一个相当简单的递归实现，这意味着它只有在您保证您的递归深度将相当低时才有用.首先检查你的树是否足够深以炸毁堆栈；如果任何节点的子节点也是它们的父节点/祖先节点，则此代码将尝试永远运行，直到耗尽堆栈.一种检查方法是跟踪 findchildren() 返回的所有节点，并确保它们永远不会重复.

Python has a fairly naïve implementation for recursion which means it is only useful when you can guarantee that your recursion depth is going to be fairly low. First check your tree really is deep enough to blow the stack; if any nodes have children which are also their parents/ancestors, this code will try to run for ever until it exhausts the stack. One way to check is to keep track of all the nodes returned by findchildren() and make sure they never repeat.

如果您的数据是正确的，而堆栈确实不够深，您将不得不将代码转换为迭代版本并手动构建您自己的堆栈.这是带有显式堆栈的代码(我尚未对此进行测试，因此可能存在错误，但它应该可以让您了解如何操作):

If your data is correct and the stack really isn't deep enough, you will have to translate the code into an iterative version and manually build your own stack. Here is your code with an explicit stack (I have not tested this so there may be bugs, but it should give you an idea of how to do it):

def tree(dad, children):
    stack = [(dad, children)]
    while stack:
        dad, children = stack.pop()
        for index, child in enumerate(children):
            childobject = nodeobject(child,dad)
            dad.childs.append(childobject)
            newchilds = findchildren(child, children)
            if len(newchilds) == 0:
                lastchild = nodeobject(newchilds,childobject)
                childobject.childs.append(lastchild)
                loopchild = copy.deepcopy(lastchild)
                while loopchild.parentNode != None:
                    print "last child"
                    result.append(loopchild.currentNode) # result global to store values
                    loopchild = copy.deepcopy(loopchild.parentNode)
            else:
                stack.append((dad, children[index:]))
                stack.append((childobject,newchilds))
                break

需要注意的一个重要特征是，我们必须将尚未在 for 循环中处理的子节点推送回堆栈，然后再推送新的子节点.

One important feature to note is that we have to push the children, that have not yet been processed in the for loop, back onto the stack before we push the new children nodes.

@Peter Gibson 提出了一个很好的观点，即您可能不想深度复制您的节点，但这不应该导致您的堆栈爆炸(只是使用大量内存而我看不出任何好处).

@Peter Gibson makes a good point that you probably don't want to deepcopy your nodes, but this should not cause your stack to blow up (just use up lots and lots of memory without any benefit I can see).

这篇关于python递归迭代超过树实现的限制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！