[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
tail recursion
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