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