I love generator and I use it a lot. Lately I've been writing some

recursive generator to traverse tree structures. After taking closer look

I have some concern on its performance.

Let's take the inorder traversal from

http://www.python.org/peps/pep-0255.html as an example.

def inorder(t):

if t:

for x in inorder(t.left):

yield x

yield t.label

for x in inorder(t.right):

yield x

Consider a 4 level deep tree that has only a right child:

1

\

2

\

3

\

4

Using the recursive generator, the flow would go like this:

main gen1 gen2 gen3 gen4

----------------------------------------------------

inorder(1..4)

yield 1

inorder(2..4)

yield 2

yield 2

inorder(3..4)

yield 3

yield3

yield 3

inorder(4)

yield 4

yield 4

yield 4

yield 4

Note that there are 4 calls to inorder() and 10 yield. Indeed the

complexity of traversing this kind of tree would be O(n^2)!

Compare that with a similar recursive function using callback instead of

generator.

def inorder(t, foo):

if t:

inorder(t.left, foo):

foo(t.label)

inorder(t.right, foo):

The flow would go like this:

main stack1 stack2 stack3 stack4

----------------------------------------------------

inorder(1..4)

foo(1)

inorder(2..4)

foo(2)

inorder(3..4)

foo(3)

inorder(4)

foo(4)

There will be 4 calls to inorder() and 4 call to foo(), give a reasonable

O(n) performance.

Is it an inherent issue in the use of recursive generator? Is there any

compiler optimization possible?