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!

Probably a dupe of How do I avoid having Python class data shared among instances? — user2357112
– user2357112, Commented Nov 14, 2015 at 22:27

Jared Mackey · Accepted Answer · 2015-11-14 22:32:35Z

2

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

answered Nov 14, 2015 at 22:32

Jared Mackey

4,2085 gold badges36 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mark Ross Over a year ago

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!

Collectives™ on Stack Overflow

Python Tree Recursion

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related