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

Re: tail recursion



>    > 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.