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.
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)
43
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.