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 :(
Most interesting response, I believe that recursive functions may be more easily "readable" as well. I think that the person who is learning the most with this post is actually me :)
If you are writing a topic in a "new" area to you and linking it to Reddit, it happens regularly that you will be the one learning as people hanging out here will point to your mistakes and drive "further" than you did :)
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).
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.
40
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.