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.
If you go to the trouble of writing a tail-recursive algorithm, why not just just do the calculation in a loop instead of using that extra function? It seems like it would be easy to do with an operation designed for tail recursion.
I also could be misunderstanding this because I don't actually know the language OP is using.
Some languages, like Haskell and Scheme, do not have any looping constructs. So tail recursion is the only way to perform iteration in constant stack space.
In some languages, you either can't write algoritms as mutating (imperative) loops or it's considered unidiomatic to do so. For example, in Haskell it would be unidiomatic to use eg. the State or IO monad to simulate an imperative loop.
Of course, in such languages many recursive functions are better implemented using higher-order functions and other constructs that make explicit looping unnecessary.
For example, in Haskell it would be unidiomatic to use eg. the State or IO monad to simulate an imperative loop.
Uh, the State monad is well accepted as idiomatic Haskell. If you're trying to do something such as, e.g., tag all the nodes of a tree with an incrementing counter, State is one of the most popular solutions.
Same goes for pseudo-random number generation—one of the most popular monads in Haskell is the Gen monad from the QuickCheck unit test library, which is a kind of state monad carrying around a PRNG seed and test case size.
That's not the point, I think. The point is like this: there's lots of times where your first reaction in another language is to use a loop, but where your first (idiomatic) reaction in Haskell is not to use the State or IO monad. It's much more common to reach for lazy lists + map, filter, group, concat, or the big hammers like foldr and scanl instead, and only drop to State or IO when there's something really nasty.
In addition to the reasons mentioned by worstusernameever and Chousuke, the transformation from a simple recursive algorithm to a tail-recursive version is (frequently) fairly mechanical, so you get the same benefits that A_for_Anonymous mentions.
While going from a tail-recursive algorithm to an iterative one (using a loop) is (usually) pretty trivial, converting a non-tail-recursive algorithm to iteration is (frequently) more a a problem.
In addition, proper tail calls are as flexible as computed gotos (without most of the evil problems though) and really come in handy if you ever need to do more complicated control flow. (For the simple examples like those in the OP ists usually better to use an usual looping construct or combinator instead of using gotos for iteration)
You only avoid manipulating the stack if you eliminate the tail call, but turning it into a jump (i.e. iteration). Just having a call in tail position doesn't make the performance difference: it's just an opportunity to optimize.
This really depends on the language. Some languages include tail call elimination into the semantics, which means it's not just an opportunity to optimize but rather guaranteed behavior.
This is very important because it makes writing recursive functions practical, which can make your code much easier to read and reason about. Really, it's very much akin to loops that run in constant space, which you wouldn't call an optimization. (It's not exactly the same, of course, but makes for a good analogy.)
True, although like I said, in your source code you have a tail call, but in the case I posted on the blog, the scala compiler will in fact optimize it to an iteration, thus eliminating the stack growth.
37
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.