[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: tail recursion
- To: rrrs-authors
- Subject: Re: tail recursion
- From: R. Kent Dybvig <email@example.com>
- Date: Fri, 20 Apr 90 14:34:47 -0500
> Date: Fri, 20 Apr 90 08:49:22 CDT
> From: Luddy Harrison <firstname.lastname@example.org>
> 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.
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)))))
This example demonstrates why it is necessary to think in terms of tail
"calls", not tail "recursion".