Python Tree Recursion

Question

I'm having some difficulties getting python to recursively print out the results from a search tree. I'm native to C++ and I'm completely familiar with using pointers to traverse such structures, but Python does more work than I'm used to. . .

In any case, I'm hoping someone will be able to help me. I'm working on implementing a heuristic to solve the Traveling Salesman Problem; however, I can't begin work on the actual heuristic until I can iterate through my tree. In any case, here's the code for the tree.

class Tree:
 branches = dict()
 def __init__(self, cities, n=0):
 if len(cities) == 1:
 nc = list(cities) # create a working list
 # grab the nth element of the list, default to head
 # Stash that as the node value
 self.node = nc[n]
 print "Complete!"
 elif len(cities) == 0:
 print "Doubly Complete!"
 else:
 nc = list(cities) # create a working list
 # grab the nth element of the list, default to head
 # Stash that as the node value
 self.node = nc[n]
 print self.node
 del nc[n] # Pop off the nth value from the list
 print "deleted city! See?"
 print nc
 c = 0 # create a counter
 for a in nc: # loop through the remaining cities
 self.branches[a] = Tree(nc, c) # generate a new tree
 c += 1 # increase the counter
 def __repr__(self, tier=1):
 ret = ("\t" * tier)
 ret += self.node
 ret += "\n"
 for a in self.branches:
 ret += self.branches[a].__repr__(tier+1)
 return ret
__str__ = __repr__

Here is where the tree is instantiated and printed:

l = ['A','B','C','D']
mine = Tree(l)
print mine

The result of printing the Tree is a RuntimeError: maximum recursion depth exceeded. I'm at my wits end when it comes to what to do next. I would certainly appreciate any help!

Oh! Believe me when I say, if I could use another method than recursion, I would. This particular heuristic requires it, though.

Thanks for any and all help!

• user2357112: Probably a dupe of How do I avoid having Python class data shared among instances?

Answer 1

This code seems to work. All I did was move the self.branches to inside the __init__. I did so following best practices while debugging. The problem was they were class members not instance members. Having a mutable datatype like dict be a class member just asks for problems.

class Tree:
 def __init__(self, cities, n=0):
 self.branches = dict()
 if len(cities) == 1:
 nc = list(cities) # create a working list
 # grab the nth element of the list, default to head
 # Stash that as the node value
 self.node = nc[n]
 print "Complete!"
 elif len(cities) == 0:
 print "Doubly Complete!"
 else:
 nc = list(cities) # create a working list
 # grab the nth element of the list, default to head
 # Stash that as the node value
 self.node = nc[n]
 print self.node
 del nc[n] # Pop off the nth value from the list
 print "deleted city! See?"
 print nc
 c = 0 # create a counter
 for a in nc: # loop through the remaining cities
 self.branches[a] = Tree(nc, c) # generate a new tree
 c += 1 # increase the counter
 def __repr__(self, tier=1):
 ret = ("\t" * tier)
 ret += self.node
 ret += "\n"
 for a in self.branches:
 ret += self.branches[a].__repr__(tier+1)
 return ret
 __str__ = __repr__
t = Tree(["SLC", "Ogden"], 1)
print t

• Mark Ross: Thanks for the help! I'll need to read up on the differences between the two so I don't make the same mistake again!