Re: tail recursion

[R. Kent Dybvig <dyb@iuvax.cs.indiana.edu>]

> Date: Fri, 20 Apr 90 08:49:22 CDT
> From: Luddy Harrison <harrison@sp21.csrd.uiuc.edu>
> 
> What precisely is meant by "properly tail-recursive"?  That is, what
> is required of an implementation, in order that it may be called
> properly tail-recursive?

How about this:

The net (modulo storage reclamation) amount of storage space consumed
by performing any sequence of tail calls p1 => p2 => ... => pn is no
more than the amount that would be consumed by performing a direct tail
call from p1 => pn.

A tail call is a procedure call occurring in "tail position".

For a lambda expression of the form (lambda formals e1 ... e2), e2 is
in tail position.

If a conditional expression of the form (if e1 e2 e3) is in tail
position, then e2 and e3 are in tail position.

If a conditional expression of the form (if e1 e2) is in tail position,
then e2 is in tail position.

A subexpression of a derived expression type is in tail position if
the derived expression is in tail position and the subexpression occurs
in tail position in the expansion of the derived expression.


Example:

The following program should not cause a memory overflow (assuming that
garbage closures created along the way are reclaimed):

    (define f (lambda (f) (lambda () ((f f)))))
    ((f f))

This example demonstrates why it is necessary to think in terms of tail
"calls", not tail "recursion".

Kent