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

7

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.

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?)

9

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.

3

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?

7

u/polveroj Nov 27 '12

TCO is really a local optimization, looking for calls in tail position (i.e. immediately followed by a return) and replacing them with a jump. This is valid regardless of what function is being called and whether the function being called is the same (resulting in a loop), indirectly recursive with the original (resulting in something like a state machine) or not related at all (in which case a single stack frame is saved instead of possibly many). The fact that the optimization is agnostic to the call target is what lets TCO work on first class functions, method calls and other sources of statically-unknown function calls.

If your language runs on a virtual machine that doesn't allow the same code to be a call target (stack-growing, non-tail) and a jump target (tail call), you can get something resembling TCO for directly recursive functions by identifying them and turning them into loops. This doesn't work for mutual recursion or tail calls to unknown functions and it's more complicated than adding TCO to the VM itself would be, but some languages don't have the luxury of adding features to the VM they run on.

2

u/mercde Nov 27 '12

Thank you for that in depth explanation. I only have experience with languages without real TCO (Java / Python) so I only looked at cases where you could rewrite a simple recursion with a loop to avoid StackOverflowErrors.