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?

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