Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Antoon Pardon]

On 07/13/2015 01:28 PM, Chris Angelico wrote:
> On Sun, Jul 12, 2015 at 8:20 AM, Ian Burnette <ian.burnette at gmail.com> wrote:
>> [ About tail recursion ]
>>
> When a function is purely tail-recursive like this, it's trivial to
> convert it at the source code level:
>
> def factorial(n):
>     acc = 1
>     while n > 0:
>         acc *= n
>         n -= 1
>     return acc
>
> The cases that _can't_ be converted this trivially are the ones that
> usually can't be converted automatically either - the best case I can
> think of is tree traversal, where one of the calls could be tail-call
> optimized:

This is not true. Tail recursion elimination can always converted
automatically. Otherwise other languages couldn't have implemted it.

> Why is it worth writing your code recursively, only to have it be
> implemented iteratively?

Because sometimes, it is easier to think about the problem recursively.

> Warping your code around a recursive solution
> to make it into a perfect tail call usually means making it look a lot
> less impressive; for instance, 

And sometimes your problem is very easily solved by a number of functions
that tail call each other but in python you will need to warp your code
around an iterative solution, in order to avoid the stack limit.

It seems warping your code is only seen as a problem when going in the
functional direction. Going into the iterative direction may take all
the warping that is needed, without comment.