[Python-Dev] Proper tail recursion
ark-mlist at att.net
Fri Jul 16 16:20:04 CEST 2004
> 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).
More information about the Python-Dev