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

tail recursion

   Date: Thu, 26 Apr 90 21:24:37 BST
   From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@nsfnet-relay.ac.uk>

   >    > 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
   >    What about cases where some storage is allocated that isn't part of
   >    the evaluation of the recursion itself?  [...]  That is, when states
   >    don't recur, the definition doesn't impose any restrictions at all
   >    on how the calls involved are implemented.
   > That is correct.  This property is quite intentional.  I believe that
   > there is very little else one can say about tail-recursion without
   > dragging in the question of representations of the data structures.

   Humm.  It's no doubt an interesting property; it's just hard to see
   that it's a definition of tail recursion.

It isn't; in fact, it relies on a pre-existing definition of what
it means for a situation to be tail-recursive.  Rather, it is a
constraint on how an implementation will behave in such situations.