performance of recursive generator

[Duncan Booth]

aurora wrote:

<generator example>
> 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)!
> 
<recursive function>
 
> 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?
> 

Do you actually have timing evidence that this is a problem with the data 
you are processing? The complexity of the algorithm may be important for 
very large data sets, but until you time it you won't know whether it is 
likely to be an issue for realistic data.

Your O(n^2) for the generator example is only n^2 if the tree is, as in 
your example, completely unbalanced. If you can keep your binary tree 
balanced it is n log n. If the tree is likely to become as wildly 
unbalanced as in your example then you should consider using a different 
data structure (e.g. a btree) where O(n log n) would be the worst case.

If you make the more realistic comparison of n calls to foo, versus nlogn 
yields the question is at what point the greater number of fast yields 
outweighs the lesser number of slow Python function calls. Until you know 
speed really is an issue, go with whichever method makes the programming 
easier.