81–87 of 87 posts
Tail recursion is a programming idea left over from the LISP era. It's from when iteration constructs were "while" and "for", and there were no "do this to all that stuff" primitives. Python doesn't really need it.
Scheme also did not just introduce tail recursion, but full tail call optimization.
Python sure does not need it, it already has a more complex iteration stuff like generators.
Earlier quoted context omitted.
Tail calls aren't always just used for some simple iteration. For example, you could have several mutually recursive functions calling each other in tail position. If you wanted to turn that into a loop, you'd have to roll all those functions into a single loop body, which would be made even less elegant due to the lack of goto statement. (TCO essentially turns a call into a goto whenever possible.)
Lots of languages can express it better though - even without gotos. For example in python you can do: while some_condition: x = one_generator(y) y = other_generator(x) where the generators yield values. No need for goto, no TCO, no magic. Even in languages like C, a nicer way to express it may be via two explicit state machines rather than going full Duff's device at this problem.
Earlier quoted context omitted.
Lots of languages can express it better though - even without gotos. For example in python you can do: while some_condition: x = one_generator(y) y = other_generator(x) where the generators yield values. No need for goto, no TCO, no magic. Even in languages like C, a nicer way to express it may be via two explicit state machines rather than going full Duff's device at this problem.
Python's generators are more magic. It's similar to some kind of COME FROM mechanism.
Earlier quoted context omitted.
Python's generators are more magic. It's similar to some kind of COME FROM mechanism.
Weird comparison. Come from has no indication on the other side that it will happen. Generators are pretty explicit with yield. On the calling side they can be explicit with a next() call.
The idea of function calls is much simpler - no yield magic necessary.
Your code is still allocating a new stack frame anyway. So no optimization is happening. You are simply avoiding a stack overflow which is not the purpose of tail-call optimization. I'm not sure if there is any advantage when language/compiler does not provide a proper tail recursive optimization.
If I wanted to do this in practice, I'd just write the trampoline out explicitly, unless I wanted to do it a huge number of times. Doing it this way only takes a couple of extra lines of code but I think that's worth it for the improvement in explicitness, which is a big help for future maintainers (possibly me!).
from functools import partial
def _tail_factorial(n, accumulator):
if n == 0:
return accumulator
else:
return partial(_tail_factorial, n - 1, accumulator * n)
def factorial(n):
result = partial(_tail_factorial, n, 1)
while isinstance(result, partial):
result = result()
return resultEarlier quoted context omitted.
Lots of languages can express it better though - even without gotos. For example in python you can do: while some_condition: x = one_generator(y) y = other_generator(x) where the generators yield values. No need for goto, no TCO, no magic. Even in languages like C, a nicer way to express it may be via two explicit state machines rather than going full Duff's device at this problem.
Python's generators are more magic. It's similar to some kind of COME FROM mechanism.