[Python-Dev] Re: Proper tail recursion
David Eppstein
eppstein at ics.uci.edu
Fri Jul 16 07:36:54 CEST 2004
In article <5.1.1.6.0.20040716000900.01e9bd40 at mail.telecommunity.com>,
"Phillip J. Eby" <pje at telecommunity.com> wrote:
> At 03:55 PM 7/16/04 +1200, Greg Ewing wrote:
>
> >We could get the benefits of that just by eliminating recursive calls
> >to ceval() when a Python function calls a Python function. I think
> >that would be a worthwhile thing to do on its own, because it would
> >mean recursion in pure Python would be limited only by available
> >memory and not an arbitrary recursion limit, which has always seemed
> >like a kludge to me.
>
> 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. A
> 4-billion element binary tree traversal only needs 32 recursion levels.
>
> So, realistically speaking, if you have hundreds of levels of recursion
> going on, you're probably doing something that should be expressed
> iteratively, or you're using 64-bit Python, in which case you probably have
> the stack space and CPU power to spare anyway. ;)
Where the recursion limit really bites me is the inability to do
recursive depth first search on big graphs. Of course, I can simulate
the stack myself and write the rest iteratively, but if I wanted to do
that I'd go back to writing in assembly language.
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
More information about the Python-Dev
mailing list