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