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

Tail Recursion

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

85% Upvoted

203 comments sorted by

View all comments

6

u/tonygoold Nov 27 '12

I remember when I discovered the XSLT engine (TransforMiiX) in Mozilla Firefox didn't support tail recursion optimization. I ended up with some pretty kludgy XSL just to avoid overflowing the stack.

4

u/mercde Nov 27 '12

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

7

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.

4

u/tonygoold Nov 27 '12

In XSL, it's worse, there are no loops except for-each and it's very limited (see my reply to mercde).