Make recursive functions tail-recursive

When writing recursive functions, consider making them tail recursive.

Reason

Non-tail recursive functions that call themselves too often end up throwing StackOverflowError at runtime.

Here’s a naïve recursive function used to compute the sum of a List[Int]:

def sum(is: List[Int]): Int = is match {
  case h :: t => h + sum(t)
  case _      => 0
}

This implementation suffers from a major flaw: on long enough lists, it will cause a runtime exception.

sum(List.range(1, 30000))
// java.lang.StackOverflowError
//   at .sum(<console>:12)
//   at .sum(<console>:13)
//   at .sum(<console>:13)
//   [...]

What happens is that, for each recursive call, the call’s context must be stored on the stack - and when a recursive function calls itself a lot, you get a stack overflow exception.

When the compiler spots a tail recursive function, however, it knows to optimise it by essentially turning it into a while loops - no more recursive calls, no more frames pushed on the stack.

Here’s our sum function, but implemented tail recursively:

def sum(is: List[Int]): Int = {

  // `loop` i our tail recursive function, keeping a running sum
  // in `acc`
  def loop(cur: List[Int], acc: Int): Int = cur match {
    case h :: t => loop(t, acc + h)
    case _      => acc
  }

  loop(is, 0)
}

And as you can see, this is now safe:

sum(List.range(1, 30000))
// res1: Int = 449985000

Exceptions to the rule

Tail recursion is a desirable property, but not an absolute requirement.

There are scenarios where “normal” recursion is more appropriate. A fairly standard example is tree traversal:

• the recursion is bounded to the height of the tree, so there’s no real risk of a StackOverflowError.
• tail-recursive functions for tree exploration are far more complicated than non tail-recursive ones.

As is often the case, this rule is more of a default decision, to be overruled when you need to.

Checked by