performance of recursive generator

[Matt Hammond]

> Is it an inherent issue in the use of recursive generator? Is there any  
> compiler optimization possible?

Hi, I could be misunderstanding it myself, but I think the short answer to  
your question is that its an inherent limitation.

> def inorder(t):
>      if t:
>          for x in inorder(t.left):
>              yield x
>          yield t.label
>          for x in inorder(t.right):
>              yield x

Using the generator you pass the tree node labels back up through each  
nested generator - therefore the deeper you are, obviously, the more  
yields it will take to pass the data back up.

As you seem to have realised, you are, in effect traversing back up the  
tree from every node you visit, in order to deliver the data.

> def inorder(t, foo):
>      if t:
>          inorder(t.left, foo):
>          foo(t.label)
>          inorder(t.right, foo):

Inherently, by using callbacks you are shortcutting this - delivering  
direct. (I assume foo is a list you're building or something similar) Of  
course there might be some cunning alternative formulation, but I can't  
think of it :-)

To optimise this away, I guess python would need to see this:

>          for x in inorder(t.left):
>              yield x

And understand that you're just asking it to pass on all yields from a  
nested generator as if they were coming from this generator.

Perhaps if there existed some kind of syntax to hint this to python it  
could optimise it away, eg:

               yield *inorder(t.left)

... but AFAIK there isn't :-( so I guess you'll have to avoid recursive  
generators for this app!



Matt

-- 

| Matt Hammond
| R&D Engineer, BBC Research and Development, Tadworth, Surrey, UK.