[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: rrrs-authors*Subject*: Re: tail recursion*From*: R. Kent Dybvig <dyb@iuvax.cs.indiana.edu>*Date*: Fri, 20 Apr 90 14:34:47 -0500

> 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

**Follow-Ups**:**tail recursion***From:*harrison@sp21.csrd.uiuc.edu (Luddy Harrison)

- Prev by Date:
**tail recursion** - Next by Date:
**re: tail recursion** - Prev by thread:
**tail recursion** - Next by thread:
**tail recursion** - Index(es):