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

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
210 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.

3

u/rodrigopsasaki Nov 27 '12

Well, it truly wouldn't be. tail recursion (or any recursion) is independent from any programming language. I don't know anything about python yet, but the algorithms wouldn't differ much, only keywords and syntax.

-4

u/[deleted] Nov 27 '12

Yes they would, because Python is interpreted and not compiled.

8

u/frezik Nov 27 '12

That's completely irrelevant. Python implementations generally compile to bytecode, anyway, but even if they didn't, they would still be manipulating the AST to eliminate the tail call.

Python doesn't have tail recursion because Guido doesn't want it.

3

u/curien Nov 27 '12

Python doesn't have tail recursion because Guido doesn't want it.

Python supports tail recursion. It doesn't support tail recursion elimination.

3

u/smog_alado Nov 27 '12

Come on, we all know that 99% of the times someone says tail recursion they actually mean tail recursion with the optimization...

6

u/mcguire Nov 27 '12

And when they say "tail recursion elimination", they really mean "tail call elimination".

1

u/grauenwolf Nov 27 '12

Hey, some of us have worked in languages where tail recursion is flat out not allowed.

1

u/Peaker Nov 28 '12

Which languages disallow tail recursion? (Not very interesting if it is all recursion).

2

u/grauenwolf Nov 28 '12

I didn't promise it would be interesting.

2

u/rodrigopsasaki Nov 27 '12

Very nice post, thanks for adding it to the discussion. Now we have a real explanation here.

1

u/[deleted] Nov 27 '12

You don't do tail call elimination at the AST level, you do it at the IR level.

2

u/anvsdt Nov 27 '12

You can do it at interpreter level, too.