Style question on recursive generators

[Carlos Ribeiro]

Hello all,

Here I am using some deeply nested, tree-like data structures. In some
situations I need to traverse the tree; the old-style way to do it is
to write a recursive method on the node class, as in:

def walk(self):
    """old-style recursive tree traversal"""
    child.do_something
    for child in childs:
        child.walk()

Of course, "do_something" can be a configurable method or action on
the node, whose actual implementation doesn't matter for this
discussion. The recursive solution is clean and readable, and that's
why its frequently preferred over the iterative solution, which (a)
requires manual housekeeping (using a stack) to work; and (b) is not
truly 'object oriented', in the sense that it does not delegate node
traversal behavior to the node being traversed.

In my last projects I've been tending towards a greater use of
generators. However, when a generator is used in the situation
described above, the end result does not 'read' as naturally:

def walk(self):
    """generator-based recursive tree traversal"""
    yield child
    for child in childs:
        for node in child.walk()
            yield node

The problem is that I need to 'chain' the yields from the subtrees to
yield back the result to the caller. It does not seem to be as elegant
as the simple recursive version; it's confusing to read, because one
has to figure out what is being yielded in the inner loop, and it's
also error-prone -- it's easy to forget to include the 'yield' in the
inner loop.

I'm now wondering which is better: to keep using old-style recursive
tree traversal code, or to chained-yield generator solution. It's more
of a stylistic decision -- I'm not concerned about raw performance at
this point, but clarity and elegancy of design are more important.

-- 
Carlos Ribeiro
Consultoria em Projetos
blog: http://rascunhosrotos.blogspot.com
blog: http://pythonnotes.blogspot.com
mail: carribeiro at gmail.com
mail: carribeiro at yahoo.com