Tail recursion in Python
chrispenner.ca
Tail recursion in Python
1–10 of 87 posts
Re: Tail recursion in Python
#2> def tail_factorial(n, accumulator=1):
> if n == 0: return 1
> else: return tail_factorial(n-1, accumulator * n)
The second line should be "if n == 0: return accumulator"
Re: Tail recursion in Python
#3> def tail_factorial(n, accumulator=1): > if n == 0: return 1 > else: return tail_factorial(n-1, accumulator * n) The second line should be "if n == 0: return accumulator"
0! == 1
EDIT: Oops. As pointed out below, the code is indeed incorrect, and my comment is irrelevant.
Re: Tail recursion in Python
#4Interesting use of exceptions.
Re: Tail recursion in Python
#5The hackyness/speed issues aside:
When compiling/transpiling/whatever between languages, I have found that relying on regular procedure calls and TCO is generally a lot simpler than having to force the looping facility of one language into the semantics of another language.
The only one I can actually imagine porting other loops to is the common lisp loop macro, but that is probably the most flexible looping facility known to man.
Edit: and oh, cool thing: racket and guile has expanding stacks and doesn't have a recursion limit other than the whole memory of the computer. This is pretty handy when implementing something like map, since you can write a non-tail-recursive procedure so that you don't have to reverse the list at the end.
Re: Tail recursion in Python
#6> def tail_factorial(n, accumulator=1): > if n == 0: return 1 > else: return tail_factorial(n-1, accumulator * n) The second line should be "if n == 0: return accumulator"
0! == 1 EDIT: Oops. As pointed out below, the code is indeed incorrect, and my comment is irrelevant.
True, but irrelevant. For all values of n > 1, that function will return 1, which is clearly not what the author intended.
Re: Tail recursion in Python
#7I'm not a pythonista, but this code seems to get rid of the recursion limitation of the interpreter. Does it actually "optimize" things and make the function take a constant space as it is calling itself?
Re: Tail recursion in Python
#8This can also be done using trampolines without using try/catch method: https://github.com/0x65/trampoline
Re: Tail recursion in Python
#9I'm not a pythonista, but this code seems to get rid of the recursion limitation of the interpreter. Does it actually "optimize" things and make the function take a constant space as it is calling itself?
It takes a constant space since it is not even recursive. The decorator makes it a non-recursive function with a loop.
It'll effectively side-steps the recursion limit in Python. For runs under the limit anyway, it'd be interesting to see whether it's any faster. It trades function call overhead for exception handling overhead.
By the way, the first example where it has `return 1` is wrong. It shoudl `return accumulator`. Clicking the GitHub link someone suggested this in December.
Re: Tail recursion in Python
#10Code snippets you won't see if you have JS disabled:
https://gist.github.com/ChrisPenner/c0b3f4feb054daa2f6370d2e...
https://gist.github.com/ChrisPenner/c958afbf6e7a763c188d8b83...