Python Recursive Iteration Exceeding Limit For Tree Implementation

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 =

Solution 1:

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 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

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 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).

Solution 2:

I'd say this block of code is the issue:

        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)

You traverse the tree until you get to a leaf (child with no children), and then you take a deepcopy of every node back to the start.

deepcopy makes a copy of the nodeobject, along with copies of it's parentNode and every child in childs. This means that every deepcopy of a nodeobject is a copy of the whole tree along with all of your data!

Consider a simple tree that is 4 levels deep, such as

AB           C
 D     E     F     G
H I   J K   L M   N O

When it gets down to the first leaf H, it makes a deepcopy of nodes H, D, B, & A - each one is a copy of the whole tree and all of your data. So you end up with 32 copies for this fairly simple structure! I can see how this quickly blows out of control.

Is there a reason you are making copies of every node? Try replacing that code with

        loopchild = lastchild
        while loopchild.parentNode != None:
            print"last child"
            result.append(loopchild.currentNode) # result global to store values
            loopchild = loopchild.parentNode