Recursion in instance method in python

Question

I am trying to define a recursive method to walk all the nodes of a tree. I defined the Tree as the following:

class Tree(object):

    def __init__(self, value, lson=None, sibling=None):
        self.value = value
        if lson:
            self.lson = Tree(lson)
        else: 
            self.lson = None

        if sibling:
            self.sibling = Tree(sibling)
        else:
            self.sibling = None

    def __str__(self):
        return str(self.value)

I have the following function that works:

def walk_tree(t):
    # walk in order
    print t
    if t.lson:
        walk_tree(t.lson)
    if t.sibling:
        walk_tree(t.sibling)
    return t

How do I turn this to an instance method?

def walk_tree(self):
    # walk in order
    print self.value
    if self.lson:
        self.walk_tree(self.lson)
    if self.sibling:
        self.walk_tree(self.sibling)
    return self

This will result in Max recursion depth error...

a. Is this how do you implement a recursive method?
b. Is there a justification here to use yield?
c. Is there a justification here to use @staticmethod which recieves a Tree instance?

darn you are right, I was wondering that it works. In earlier versions, I saw File "trees1.py", line 59, in walk_tree self.walk_tree() RuntimeError: maximum recursion depth exceeded ` — oz123
– oz123, Commented Apr 27, 2014 at 8:56

Martijn Pieters · Accepted Answer · 2014-04-27 09:01:03Z

1

Your recursive method is not recursive. It calls a global walk_tree() that may or may not be recursive itself.

To make a method properly recursive, reference the method on the sub-nodes:

def walk_tree(self):
    # walk in order
    print self.value
    if self.lson:
        self.lson.walk_tree()
    if self.sibling:
        self.sibling.walk_tree()
    return self

This only ever prints values, it doesn't return anything but the top-level node to the initial caller.

yield can help give access to the values efficiently, but you do need to remember to yield recursive calls:

def walk_tree(self):
    # walk in order
    yield self.value
    if self.lson:
        for res in self.lson.walk_tree():
            yield res
    if self.sibling:
        for res in self.sibling.walk_tree():
            yield res

or, using Python 3.3 or up, with yield from generator delegation:

def walk_tree(self):
    # walk in order
    yield self.value
    if self.lson:
        yield from self.lson.walk_tree()
    if self.sibling:
        yield from self.sibling.walk_tree()

A static method is just a namespaced function; your original walk_tree() global could be made into a static method, sure, but there is little point unless you feel the namespace clarifies your API.

edited Apr 27, 2014 at 9:01

answered Apr 27, 2014 at 8:54

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

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

4 Comments

Martijn Pieters Over a year ago

@Oz123: Actually, it should have given you an exception about having an argument too many; I've corrected it to delegate to the child nodes.

oz123 Over a year ago

Thank you! This was the missing piece. Now I have a problem with your walk_tree with yield. It runs, but finishes with an error: TypeError: 'Tree' object is not iterable. I could probably wrap it with Try ... Except, it just feels weired.

Martijn Pieters Over a year ago

@Oz123: then self.lson.walk_tree() or self.sibling.walk_tree() is not a generator but returns a Tree object. Make sure these are all the same type or at least implement walk_tree() the same way; as a generator.

oz123 Over a year ago

Ok, now everything works. The function, instance method, and instance method with generator. Thanks for that.

Collectives™ on Stack Overflow

Recursion in instance method in python

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related