performance of recursive generator

[aurora]

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?
-- 
http://mail.python.org/mailman/listinfo/python-list