[Python-Dev] Re: Proper tail recursion

David Eppstein eppstein at ics.uci.edu
Fri Jul 16 07:36:54 CEST 2004

In article < 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