# Recursive Generator Question

Jp Calderone exarkun at divmod.com
Fri Sep 3 05:33:08 CEST 2004

```Paul Chiusano wrote:
> I've been playing around with generators and have run into a
> difficulty. Suppose I've defined a Node class like so:
>
> class Node:
> 	def __init__(self, data=None, left=None, right=None):
> 		self.children = []
> 		self.children.append(left)
> 		self.children.append(right)
> 		self.data = data
>
> 	def __iter__(self): return self
>
> 	def next(self):
>         """ Returns iteration over terminal nodes of this tree. """
> 		if self.data:
> 			yield self
> 		else:
> 			for child in self.children:
> 				for terminal in child:
> 					yield terminal
>
>
> And then suppose I create a little binary tree like so:
>
> a = Node('a')
> b = Node('b')
> c = Node('c')
> d = Node('d')
> ab = Node(left=a, right=b)
> cd = Node(left=c, right=d)
> abcd = Node(left=ab, right=cd)
>
> for termNodes in abcd:
> 	print termNodes.data # gives an error
>
> when I do this, I get the following error:
> Traceback (most recent call last):
>   File "C:\Documents and Settings\Paul
> Chiusano\workspace\sandbox\hello.py", line 69, in ?
>     print termNodes.data
> AttributeError: 'generator' object has no attribute 'data'
>
> For some reason, that iteration is returning generators instead of
> leaves. Curiously, if I replace that for loop with
>
> for termNodes in terminals(abcd): # see definition below
> 	print termNodes.data # no problem!
>
> then it actually prints out:
> a
> b
> c
> d
>
> Here's the definition of terminals--pretty much identical to next.
>
> def terminals(t):
> 	""" Returns an iteration over the leaves of a tree, t """
> 	if t.data: # if I have data, then I'm a terminal node
> 		yield t
> 	else:
> 		for child in t.children:
> 			for terminal in terminals(child):
> 				yield terminal
>
> Am I missing something? Or is it not possible to define recursive
> generators in this way?

The generators are a red herring :)  Iterating over an object calls
__iter__ on the object, then repeatedly calls next on the object
returned by __iter__.  Each object next returns is taken as a value for
iteration.

So, if we examine your node class, we see that when __iter__ is
called, the same object is returned.  When next is called on the node
class, a generator is returned.  Oops.  Throw away your current __iter__
method and rename your next method __iter__.  Now when __iter__ is
called, it will return a generator, and when next is called on the
generator, you will get the leaf nodes you were looking for.

Jp

>
> Thanks,
> Paul

```