# A new module for performing tail-call elimination

Terry Reedy tjreedy at udel.edu
Thu Jul 16 21:45:45 CEST 2015

```On 7/16/2015 2:02 PM, Ethan Furman wrote:
> On 07/16/2015 06:35 AM, Antoon Pardon wrote:

>> Here is one way to do the odd, even example.
>>
>> def even(n):
>>      return odd_even('even', n)
>>
>> def odd(n):
>>      return odd_even('odd', n)
>>
>> def odd_even(fn, n):
>>      while fn is not None:
>>          if fn == 'even':
>>              fn, n = (None, True) if n == 0 else ('odd', n - 1)
>>          elif fn == 'odd':
>>              fn, n = (None, False) if n == 0 else ('even', n - 1)
>>          else:
>>              raise ValueError("Unknown state: %s" % fn)
>>      return n
>
> Wow -- definitely uglier and less easy to understand than the original

What you call ugly is an example of the core of the proof that
alternation and indefinite while looping are enough for turing
completeness, and that no recursive syntax is needed.  Another way to
put it is that while loops perform recursion in the operational sense,
as opposed to the syntactical sense.

--
Terry Jan Reedy

```