Recursive Generator Question

Paul Chiusano pchiusan at umich.edu
Fri Sep 3 04:39:26 CEST 2004


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?

Thanks,
Paul



More information about the Python-list mailing list