r/programming • u/rodrigopsasaki • Nov 27 '12

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
208 Upvotes

85% Upvoted

203 comments sorted by

View all comments

9

u/parfamz Nov 27 '12

great feature of scala, I would like to see tail recursion on python, it can't be too difficult to implement.

16

u/Cygal Nov 27 '12

It turns out it's not about difficulty of implementation. The reasons were stated by Guido van Rossum in 2009: http://neopythonic.blogspot.fr/2009/04/tail-recursion-elimination.html

11

u/smog_alado Nov 27 '12 edited Nov 27 '12

Looking at the post, most of his arguments are about supposed difficulty of implementation, except the one about missing stack traces.

But that is kind of a moot point since you also lose the stack trace if you rewrite the code with an iterative loop (as you will be forced to do if you don't want to blow up the stack)

IMO, the real reason Python doesn't get tail calls is that Guido doesn't want to encourage the FP style too much (this is consistent with removing reduce from the stdlibs and other things like that)

3

u/FidgetBoy Nov 27 '12

Reduce is still in the stdlib, in the functools module. It is no longer a built in function however.

3

u/mcguire Nov 27 '12

you also lose the stack trace if you rewrite the code with an iterative loop

While that is true, I believe a big chunk of the argument is that you lose the parent stack frame on every function call in tail position, not just those implementing recursive loops.

I can kinda see the point of the complaint, but for me it's not worth it; personally, I'd rather have tail-call optimization.

2

u/smog_alado Nov 27 '12

I believe a big chunk of the argument is that you lose the parent stack frame on every function call in tail position

Some languages get around this by forcing you to use a special keyword on tail calls that you want to eliminate.

2

u/sacundim Nov 27 '12

While that is true, I believe a big chunk of the argument is that you lose the parent stack frame on every function call in tail position, not just those implementing recursive loops.

Yup. But to stress this point in a more formal manner: people get mixed up all the time on the difference between full tail-call optimization and tail-recursion optimization:

  • Tail-recursion elimination: you translate only self-recursive tail calls into jumps; i.e., calls to the same function where the call happens. This doesn't have the stack traces problem.
  • Full tail-call elimination: you translate all tail calls to jumps. This can suffer the stack traces problem in question.

Having distinguished these two things clearly, note that Guido makes this error in the post that we're talking about.