Tail recursion, was: processing character entities

[David Carlisle <davidc@xxxxxxxxx>]

> A couple of simple examples would be very much 
> appreciated here David C.  

I see Brandon replied anyway, but perhaps a non lisp example ...

The clasic functional programing example (whatever concept you are trying
to show) is factorial. 

factorial(1) = 1
factorial(2) = 2 * 1
factorial(3) = 3 * 2 * 1
etc (it grows big, fast:-)

Now the obvious recursive defintion of this 

factorial (n) =
  if n = 1
    1
  else
    n * factorial (n-1)

However this is non tail recursive, when making the recursive call to
evaluate factorial (n-1) the system has to stack up the state of all the
local variables in the function (just n  here) as it needs the current
local value of n after the recursive call comes back.

To rewrite this in a tail recursive manner, the standard trick is to
introduce a supplementary function that builds up the value in the
_arguments_ not in the recursion stack, like so

factorial (n) = 
  factorial_helper (n,1)



factorial_helper (n,result) =
  if n =1
     result
  else
    factorial_helper (n-1, n * result)



This time round, the system knows that it does not need any of
factorial_helper local information after it has made the recursive call,
so it does not need to stack that information, and can treat the
recursion as syntactic sugar for a loop.


There is a formal theory you can apply to decide which functions may be
written into tail recursive form (and you may even hope that an
optimising compiler would rewrite that first `bad' form into the tail
recursive form on its own). But basically you can't do it if there is
essential use made of more than one recursive call, eg to do a depth
first walk over a binary tree doing a recursive call to walk each branch,
you can make one of the calls tail recursive, but the other is bound to
use up recursion stack.

David
(Given the total lack of dsssl in this posting, probably best to stop
this thread:-)


 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist