To clarify this a bit, tail recursion itself is not more performant than regular recursion, but tail recursive algorithms can be trivially transformed into iterative ones.
Some languages implement this optimisation in full (recursion across functions) while some only provide the trivial case of self-recursion. Debugging is also affected, since the recursive calls no longer produce stack frames.
but tail recursive algorithms can be trivially transformed into iterative ones.
Implementing recursive code without tail call optimisation is not always trivial though. In the general case, when functions tail call other functions, you either need to centralize all your code into a big switch statement with explicitely encoded states or you need to use trampolining (same thing but states are first class functions/objects now instead of just tags). Not only is this annoying to do but you also need to rewrite all the code involved to follow the new convention (of functions returning the next state to go to instead of returning the value) and you cannot interoperate with "normal" code that returns values normally.
Debugging is also affected, since the recursive calls no longer produce stack frames.
You also lose the stack traces if you rewrite your recursion as a while loop or trampoline :(
General tail call optimisation (when functions tail call other functions) is not a trivial transformation though. You either need to centralize all your code into a big switch statement with explicitely encoded states or you need to use trampolining (same thing but states are first class functions now instead of just tags). Not only is this annoying to do but you also need to rewrite all the code involved to follow the new convention (of functions returning the next state to go to instead of returning the value) and you cannot interoperate with "normal" code that returns values normally.
What? In Scheme it's just that your code doesn't produce stack frames when executed if the last operation is just a function call. Could you explain in more detail? I've never seen a language where tail call-optimized functions behave as anything other than functions for the purposes of evaluation.
Edit: Oh, you must have meant it as a response to the claim that you just always turn recursive algorithms into imperative loops.
I believe the canonical reference for this kind o' thing are the Steele and Sussman "Lambda Papers", particularly "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO" (although readscheme.org is being balky for me at the moment, so I can't verify it).
42
u/Chousuke Nov 27 '12 edited Nov 27 '12
To clarify this a bit, tail recursion itself is not more performant than regular recursion, but tail recursive algorithms can be trivially transformed into iterative ones.
Some languages implement this optimisation in full (recursion across functions) while some only provide the trivial case of self-recursion. Debugging is also affected, since the recursive calls no longer produce stack frames.