[Python-Dev] Proper tail recursion

[Andrew Koenig]

> Yeah, but it's a *useful* kludge to have a recursion limit.  Most
> algorithms that are "sensibly" recursive have some fan-out at each
> recursion level, such that the total recursion needed is something like
> log2N.  So as N grows, the relative amount of recursion shrinks.

Not if the data structure is lopsided -- perhaps intentionally so.  Remember
the typical usage of a Lisp list, which is really a binary tree in which the
depth of each left-hand subtree is usually very small (typically 1).