New tail recursion decorator
Terry Reedy
tjreedy at udel.edu
Fri May 12 22:02:36 CEST 2006
"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
More information about the Python-list
mailing list