Tail recursion to while iteration in 2 easy steps

[Duncan Booth]

Neil Cerutti <neilc at norwich.edu> 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.

-- 
Duncan Booth http://kupuguy.blogspot.com