[Python-Dev] Tail recursion

Brett C. bac at OCF.Berkeley.EDU
Wed Nov 26 01:48:53 EST 2003


Guido van Rossum wrote:
>>>Tail Recursion
>>>--------------
>>>from Me (my brain)
>>>
>>>Have proper tail recursion in Python.  Would require identifying where
>>>a direct function call is returned (could keep it simple and just do
>>>it where CALL_FUNCTION and RETURN bytecodes are in a row).  Also have
>>>to deal with exception catching since that requires the frame to stay
>>>alive to handle the exception.
>>>
>>>But getting it to work well could help with memory and
>>>performance. Don't know if it has been done for a language that had
>>>exception handling.
>>
>>How is this different from stackless?
> 
> 
> AFAIK Stackless only curtails the *C* stack, not the chain of Python
> frames on the heap.
> 
> But I have a problem with tail recursion.  It's generally requested by
> new converts from the Scheme/Lisp or functional programming world, and
> it usually means they haven't figured out yet how to write code
> without using recursion for everything yet.  IOW I'm doubtful on how
> much of a difference it would make for real Python programs (which,
> simplifying a bit, tend to use loops instead of recursion).  And also
> note that even if an exception is not caught, you'd like to see all
> stack frames listed when the traceback is printed or when the debugger
> is invoked.
> 

I mostly agree with everything Guido has said.  It probably should only 
be used when -OO is switched on.  And yes, iterative solutions tend to 
be easier to grasp.

I have to admit that I partially come from a Scheme world (learned it 
*very* shortly after I started the process of learning Python).  So I 
have always had a slight soft spot for elegant recursive solutions.

I will file this idea in the "not that popular" pile.  =)

-Brett




More information about the Python-Dev mailing list