February 27, 2011

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`): Double = {
var queue: List` = 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.

```
@annotation.tailrec def recursive(expression: List`, queue: List` = 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`

.