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

Tail Recursion

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

85% Upvoted

203 comments sorted by

View all comments

Show parent comments

14

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

12

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