[Python-Dev] Proper tail recursion (original) (raw)

Andrew Koenig 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 mailing list