<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] >>>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 -- http://mail.python.org/mailman/listinfo/python-list
