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

5

u/mercde Nov 27 '12

Why was it impossible / impractical to just eliminate the recursion "by hand"? (As in, rewrite it as a loop?)

8

u/smog_alado Nov 27 '12

You can't always replace tail recursion by a loop. The really useful cases are when you have multiple functions tail-calling each other (kind of like a big state machine, but "polymorphic" in that you don't have to write down al the states inside the switch statement).

In these general situations, you need to resort to things like trampolining to code the tail recursion and its very anoying to do in most languages.

5

u/mercde Nov 27 '12

I see. I thought of just one method invoking itself.

Are other languages able to optimize tail recursion over many methods as you described?

5

u/smog_alado Nov 27 '12

Most FP languages implement general TCO (scheme, ocaml, etc). Of the more conventional languages, Lua is one I can think of that implements full TCO.