Tail recursion to while iteration in 2 easy steps

[Duncan Booth]

Ian Kelly <ian.g.kelly at gmail.com> wrote:

> On Fri, Oct 4, 2013 at 4:41 AM, Ian Kelly <ian.g.kelly at gmail.com> wrote:
>> There is no doubt that it's a tail call.  Whether it is recursion is
>> irrelevant to optimizing it.  The reason we talk about "tail call
>> recursion" specifically is because the recursive case is the one that
>> makes the optimization worthwhile, not because the recursion is
>> necessary to perform the optimization.
>>
>> It is possible that fact is recursive but that some_decorator adds
>> additional stack frames that are not tail calls and not optimizable.
>> If this were the case, then the recursion would still eventually hit
>> the stack limit, but there would still be benefit in optimizing the
>> "fact" frames, as it would increase the allowable depth before the
>> stack limit is reached.  So I see no reason to check the identity of
>> the called function before optimizing the tail call.
> 
> On the other hand, if you start optimizing every tail call and not
> just the recursive functions, then I can see where that could start to
> get problematic for debugging -- as arbitrary functions get removed
> from the stack traces just because they happened to end in tail calls.

Quite so. Losing some stack frames in the traceback because tail recursion 
was optimised is probably no big deal. Losing arbitrary stack frames 
because of a more widespread tail call optimisation would not IMHO fit with 
the spirit of Python except possibly as an optional optimisation that was 
off by default.


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