Home Original page

Teaching : Python, Scheme, Java...

Bjorn Pettersen BPettersen at NAREX.com
Fri Apr 18 10:52:31 EDT 2003 
> From: Alex Martelli [mailto:aleax at aleax.it] 
> 
> Donnal Walter wrote:
> 
> > 
> > What is the difference between "recursive calls" and "tail 
> > recursion"? Sometimes I have written methods that call the 
> > same method on a parent or child object, with the depth of 
> > recursion being limited by a method of the same name NOT 
> > calling itself. In the past I have thought of this
> > as tail recursion. Is this incorrect?
> 
> A function-call is "tail" if it's the last thing the caller does,
> i.e., basically, if the caller executes "return somefunction(args)"
> or a semantically equivalent sequence.
> 
[..recursive..]
> 
> A function-call is "tail recursive" if it's tail and recursive.
> Such calls can be optimized by avoiding the allocation of a new
> stack frame -- the same frame object that's already on the
> stack to handle this specific call can be re-used (if you're
> willing to lose traceback information -- Python currently does
> not allow that).

[To digress, elaborate, use my MS for something :-)] It's acutally more
general. Any tail calls (recursive or not) can be optimized, trivially
(assuming the return address is stored in sp, etc.), instead of:

   return f()

being compiled to (A) -- excuse my shorthand:

         push sp, loc1
         jump f
   loc1: pop sp
         reg1 = pop fn_result_stack # 1
         push reg1, fn_result_stack # 2
         jump sp

(1 and 2 would disappear with a peephole optimizer, assuming there is
one) tail call optimization creates (B):

         jump f

with the last two lines of f looking like the last two lines of (A) the
semantics are the same.

[[Now what if you came up with an algorithm that converted any function
to a function with tail call? Your code for return would be really fast,
it would never "return" to a previous state, you wouldn't need a stack
anymore, implementing continuations would be trivial... They did it for
SML, and the various steps, algorithms, etc. are nicely described in:

   Compiling with Continuations, Andrew Appel
   Cambridge University Press 1992, ISBN 0-521-41695-7

which is one of the more interesting books I read in college both for
language and compiler theory (couldn't find an online-ref).]]

-- bjorn
More information about the Python-list mailing list