Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #93754 > unrolled thread

Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-13 14:00 +0200

#93754 — Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)

On 07/13/2015 01:28 PM, Chris Angelico wrote:
> On Sun, Jul 12, 2015 at 8:20 AM, Ian Burnette <ian.burnette@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.

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web