# performance of recursive generator

aurora aurora00 at gmail.com
Thu Aug 11 06:06:22 CEST 2005

```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?

```