Tail recursion to while iteration in 2 easy steps

[Jussi Piitulainen]

Duncan Booth writes:

> Neil Cerutti wrote:
> > On 2013-10-03, Duncan Booth <duncan.booth at invalid.invalid> wrote:
> >> It isn't hard to imagine adding a TAIL_CALL opcode to the
> >> interpreter that checks whether the function to be called is
> >> the same as the current function and if it is just updates the
> >> arguments and jumps to the start of the code block.
> > 
> > Tail call optimization doesn't involve verification that the
> > function is calling itself; you just have to verfify that the
> > call is in tail position.
> 
> You misunderstood me. As usually implemented tail call recursion
> doesn't require verifying that the function is calling itself, but
> in Python the function could be rebound so a check would be a
> necessary protection against this unlikely situation. Consider this
> Python:
> 
> @some_decorator
> def fact(n, acc=1):
>    if n <= 1:
>        return acc
>    return fact(n-1, n*acc)
> 
> Is that tail recursion or not?
> 
> You cannot tell whether or not that is tail recursion unless you
> know the definition of 'some_decorator' and even then the answer may
> vary from run to run.

Ignoring the decorator, fact(n-1, n*acc) is in a tail position because
it follows the keyword return. It doesn't matter what function fact is
at the time: the remaining action in the caller is to return.

Tail positions, with respect to enclosing code, are defined
syntactically.