New tail recursion decorator

[Terry Reedy]

"Alexander Schmolck" <a.schmolck at gmail.com> wrote in message 
news:yfsy7x7tb9q.fsf at oc.ex.ac.uk...
> Duncan Booth <duncan.booth at invalid.invalid> writes:
>> Tail recursion is when a function calls itself and then immediately 
>> returns
>> the result of that call as its own result.

Which means that the value returned by the base case is returned unchanged 
to the original caller through the stack of returns.  Which means that the 
return stack can potentially be compressed to just one return.

> I think the definition is broader than that so that these two functions 
> would
> also be tail-recursive (i.e. the tail call doesn't have to be a self-tail
> call; I might be mistaken, don't have a good reference at hand; however
> "properly tail recursive" certainly refers to being able to do the below
> without exhausting the stack even for large n, not just transforming 
> self-tail
> calls to a loop, which is sort of limited usefulness anyway):
>
> def even(n):
>    return n == 0 or not odd(n-1)
>
> def odd(n):
>    return n == 1 or not even(n-1)

No, these are not even mutually tail-recursive, assuming that that would 
make sense.  You are calling the not operator function on the results of 
the recursive calls before returning them.  The following *is* 
tail-recursive:

def even(n):
    assert n >= 0
    if n >=2: return even(n-2)
    return bool(n)

The recursive call is effectively a goto back to the top of the function, 
with n reduced by 2.  This looping continues until n < 2.  So in Python, we 
would usually write

def even(n):
    assert n >= 0
    while n >= 2: n -=2
    return bool(n)

Terry Jan Reedy