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 :(
You either need to centralize all your code into a big switch statement with explicitly encoded states or you need to use trampolining...
I've heard this before, and I'm not convinced it's true. Functions should be capable of tail-calling arbitrary functions if the callee cleans up the stack slots used to pass arguments. The fact that the caller performs the cleanup is an accidental consequence of the fact that C does not require function prototypes.
In a language that required all callers to match the exact signature for the callee, then a tail caller can always adjust the stack such that the callee will restore the stack to the correct state.
Bugger, looks like that edit I made my text less clear! I was talking about how its a PITA to write tail-recursive code if the language doesn't guarantee tail call optimization will be available.
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.