python recursive iteration exceeding limit for tree implementation

Question

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)

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

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 ?

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

Answer 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

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