home

Tail Recursion in Scala

With tail call optimization, a compiler can convert certain types of recursive functions into loops which won't blow up the stack when the number of recursive calls is high. The key is for the recursive call to be the last execution within the recursive method.

Scala 2.8 added the @scala.annotation.tailrec annotation, which notifies the compiler that a given method is meant to use tail recursion, and that a compiler error is to be thrown if the method cannot be so optimized.

The following method iteratively evaluates simple arithmetic expressions in Postfix notation.

def iterative(elements: List[Any]): Double = {
  var queue: List[Double] = Nil

  for (e <- elements) e match {
    case operand: Double   => queue = operand :: queue
    case operation: String => val result = operation match {
        case "+" => queue.tail.head + queue.head
        case "-" => queue.tail.head - queue.head
        case "*" => queue.tail.head * queue.head
        case "/" => queue.tail.head / queue.head
      }
      queue = result :: queue.tail.tail
  }

  queue.head
}

To evaluate the expression (1 + 2) * (3 - 4), it can be called with a List of these elements:

scala> iterative(List(1.,2.,"+",3.,4.,"-","*"))
res0: Double = -3.0

This algorithm can be easily converted into the following tail recursive method.

@scala.annotation.tailrec def recursive(expression: List[Any], queue: List[Double] = Nil): Double = {
  expression.head match {
    case operand: Double   => if (expression.tail == Nil) operand else recursive(expression.tail, operand :: queue)
    case operation: String => val result = operation match {
        case "+" => queue.tail.head + queue.head
        case "-" => queue.tail.head - queue.head
        case "*" => queue.tail.head * queue.head
        case "/" => queue.tail.head / queue.head
      }
      recursive(result :: expression.tail, queue.tail.tail)
  }
}

It runs on the same input as its iterative counterpart:

scala> recursive(List(1.,2.,"+",3.,4.,"-","*"))
res1: Double = -3.0

Note that I used the explicit classpath location under the implicit @scala.annotation.tailrec. I could have also added import scala.annotation.tailrec and left the annotation as @tailrec.