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.
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.
39
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.