Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Chris Angelico]

On Mon, Jul 13, 2015 at 10:00 PM, Antoon Pardon
<antoon.pardon at rece.vub.ac.be> wrote:
> 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.

Yes, when it's in the pure form of an actual tail call. Most recursion
isn't, so you have to warp your code until it is (like adding the
'acc' parameter, which is NOT logically a parameter to the factorial
function).

>> 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.

Can you give me an example that (a) makes a lot more sense recursively
than iteratively, and (b) involves just one tail call?

>> 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.

Example, please? In all my Python programming, I've never hit the
stack limit outside of deliberate playing around (or accidental
infinite recursion, which means it's doing its job).

> 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.

That's because I've never seen code that warps more for iteration than
it does for programming in general. Again, example please?

ChrisA