Building a generator from a recursive algorithm

Question

I have a recursive method that I'm using to walk over a red black tree, and store various node information (in the list storage).

def _walk (self, storage, func, starting_node) :
    if starting_node is not self._nil :
        self._walk(storage, func, starting_node.left)
        storage.append(func(starting_node))
        self._walk(storage, func, starting_node.right)

However, I'd like to re-implement this method so that it builds a generator (from what I understand this should save both time and memory). What's the "best" way of doing that?

I don't think it's going to save you much - unless you are meaning to make storage a generator instead of a list. — John La Rooy
– John La Rooy, Commented Nov 5, 2012 at 3:50
gnibbler, that's exactly what I meant. Thanks for making me clarify. — rectangletangle
– rectangletangle, Commented Nov 5, 2012 at 3:57

John La Rooy · Accepted Answer · 2012-11-08 09:57:12Z

2

Begin by decoupling the action from the walking

def _walk (self, starting_node) :
    if starting_node is not self._nil :
        for x in self._walk(starting_node.left):
            yield x
        yield starting_node
        for x in self._walk(starting_node.right):
            yield x

def traverse(self):
    starting_node = ???     # maybe these are passed as
    func = ???              # parameters to traverse
    for node in self._walk(starting_node):
        yield func(node)

traverse is roughly equivalent to

imap(func, self._walk(starting_node))

or this generator expression

(func(x) for x in self._walk(starting_node))

You can reduce the amount of stack used by manually optimising the tail recursion

def _walk (self, starting_node) :
    while starting_node is not self._nil :
        for x in self._walk(starting_node.left):
            yield x
        yield starting_node
        starting_node = starting_node.right

edited Nov 8, 2012 at 9:57

answered Nov 5, 2012 at 3:44

John La Rooy

306k54 gold badges378 silver badges513 bronze badges

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

2 Comments

georg Over a year ago

If I'm not mistaken, recursive calls to _walk won't yield anything.

John La Rooy Over a year ago

@thg435, you were not mistaken - fixed.

light · Accepted Answer · 2012-11-05 03:49:52Z

2

def _walk (self, func, starting_node) :
    if starting_node is not self._nil :
        for x in self._walk(func, starting_node.left) :
            yield x
        yield func(starting_node)
        for x in self._walk(func, starting_node.right) :
            yield x

answered Nov 5, 2012 at 3:49

light

4212 silver badges2 bronze badges

Collectives™ on Stack Overflow

Building a generator from a recursive algorithm

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related