Yielding a chain of values

[Terry Reedy]

<aurora00 at gmail.com> wrote in message 
news:1126285038.776094.66550 at o13g2000cwo.googlegroups.com...
>>>unless you are going many levels deep
> (and that's usually a design smell of some kind)
>
> No, its not a bug. its a feature! See the discussion in the recursive
> generator thread below:
http://groups.google.com/group/comp.lang.python/browse_frm/thread/4c749ec4fc5447fb/36f2b915eba66eac?q=recursive+generator&rnum=1#36f2b915eba66eac
>
> In my opinion, traversing recursive data structure is where generator
> shine best. Alternative implementation using iterator is lot more
> difficult and lot less elegant. Unfortunate the right now recursive
> generator would carry a price tag of O(n^2) to the level of depth.

The problem with asymptotic 'big O' notation is that is leaves out both the 
constant multiplier and lesser terms and promotes the misperception that 
'lower order' asymtotic behavior is always preferable.  But much real 
computation is done with small and effectively non-asymptotic values where 
the omitted components *are* significant.

In this case, the O(depth^2) cost applies, I believe, to resumptions (and 
yields) of suspended generators, which are *much* faster than function 
calls, so that the omitted multiplier is relatively small.  Given that 
there is also at least one function call cost for each tree node, I expect 
one would need a somewhat deep (intentionally vague without specific timing 
data) and unbalanced tree for the resume price to be worrisome.

In any case, having an easily written and understood version can help in 
testing a faster and more complicated version, especially on random, 
non-corner case examples.

Terry J. Reedy