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 ?

• Jeff Tratner: Have you investigated whether you're correctly descending the tree? From what you're describing, it sounds like findchildren might always find new children (and so the function will never actually exhaust itself)
• LuckyStarr: @JeffTratner - after all of you pointing me towards findchildren...I did a little more digging and it seems that was the problem. Thanks.

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

• LuckyStarr: thanks a bunch. I didn't use any copy function and modified the code to better take care of the findchildren() and it worked. Earlier when I had deepcopy and error in the findchildren...it used to give me "MAX recursion depth reached" in a split second and now after the fix the program funs for 20 mins and gives me correct answer and the recursive limit is still not violated. Don't understand how does that happen ??? Also thanks for the stack example, I will try to implement it "just because"

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

• LuckyStarr: I replaced the deepcopy with the simple assignment but my program STILL has issues. In the beginning phase of my project, this simple assignment did not work so I thought I should make a brand new copy of this object.
• Peter Gibson: @LuckyStarr can you edit your question to add some sample data and the findchildren function?
• LuckyStarr: So now after replacing deepcopy and modifying some code for the findchildren()...I've managed to fix the issue. Thanks for your help.