Scala Note 22: Tail Recursion

A function directly call itself as its last action, is called tail recursive.

Tail-recursive is the easiest kind of recursion to optimize by conversion into a loop. Loops eliminate the potential of a stack overflow, and they improve performance by eliminating the recursive function call overhead.
The scala compiler detects tail recursion and replace it with a jump back to the beginning of the function, after updating the function parameters with the new values.
A tail-recursive function will not build a new stack frame for each call; all calls will execute in a single frame.

@tailrec
def boom(x: Int): Int =
     if (x == 0) throw new Exception("boom!")
     else boom(x-1) + 1

This function is not tail recursive, because it performs an increment operation after the recursive call.

Scala only optimizes directly recursive calls back to the same function making the call, rather than the indirect recursion.

It turns out that foldLeft and reduceLeft have an important advantage over foldRight and reduceRight: the left traversals are tail-call recursive, so they can benefit from Scala's tail-call optimization.

The tail-call optimization won't be applied when a method that calls itself might be overridden in a derived type. Hence, the recursive method must be defined with the private or final keyword, or it must be nested in another method.