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

*To*: halstead@crl.dec.com*Subject*: tail recursion*From*: gls@Think.COM (Guy Steele)*Date*: Mon, 23 Apr 90 17:38:10 EDT*Cc*: rrrs-authors, halstead@crl.dec.com, harrison@sp21.csrd.uiuc.edu*In-Reply-To*: halstead@crl.dec.com's message of Mon, 23 Apr 90 16:57:12 EDT <9004232057.AA01293@crlrhh.crl.dec.com>

I have a different definition to propose. Suppose we enumerate the kinds of things that are *not* tail-recursive: evaluation of the predicate part of an IF and evaluation of the subexpressions of a call, for example. Suppose also that we can agree what we mean by the state of a program (including all observable data structures, the remainder of the computation to be performed, etc.). Then I define an implementation to be properly tail-recursive if, for every program state P, if continued execution eventually causes state P to recur, and every non-tail-recursive evaluation begun since the first occurrence of state P has completed before the second occurrence of state P then state P will recur indefinitely many times without running out of resources An interesting question is whether we can show the two proposed definitions to be equivalent or otherwise related. --Guy

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

**References**:**Re: tail recursion***From:*halstead@crl.dec.com

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