performance of recursive generator

[aurora]

On Thu, 11 Aug 2005 01:18:11 -0700, Matt Hammond  
<matt.hammond at rd.bbc.co.uk> wrote:

>
>> 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.

...

> 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!


That would be unfortunately. I think generator is most elegant in  
traversing recursive structure. It is non-trivial to use most other  
methods. But the O(n^2) price tag is a big caveat to keep in mind.

Of course I agree we should not optimize prematurely. I'm not about to  
rewrite my recursive generators just yet. But O(n^2) complexity is  
something important to bear in mind. It doesn't necessary cause problems  
in practice. But it might.