Using @tailrec to Write Safe, Stack‑Free Recursive Scala Code

The problem: deep recursion blows the stack

When a recursive method calls itself as its last operation, the JVM still creates a new stack frame for each call unless the compiler can rewrite the recursion into a loop. With a naïve recursive sum over a List, a list of a few hundred thousand elements already triggers a StackOverflowError. This forces developers to either increase the JVM stack size (which only postpones the problem) or abandon recursion altogether.

What @tailrec actually does

The @tailrec annotation is a compile‑time checker. If the annotated method’s recursive call is in tail position – meaning nothing happens after the call returns – the Scala compiler replaces the recursion with a tight loop (bytecode goto or while). If the call is not in tail position, compilation fails with an explicit error, preventing accidental stack‑growth. No runtime overhead is added; the generated bytecode is indistinguishable from a hand‑written while loop.

Applying the annotation to a list fold

Consider a simple sum of integers in a List. The naïve version is not tail‑recursive because the addition happens after the recursive call returns.

def sumNaive(xs: List[Int]): Int = xs match {
  case Nil => 0
  case y :: ys => y + sumNaive(ys) // addition after recursion → not tail position
}

To make it tail‑recursive we carry an accumulator.

import scala.annotation.tailrec


def sumTail(xs: List[Int]): Int = {
  @tailrec
  def loop(remaining: List[Int], acc: Int): Int = remaining match {
    case Nil => acc
    case y :: ys => loop(ys, acc + y) // recursive call is the last operation
  }
  loop(xs, 0)
}

The inner loop method is annotated; the outer method hides the accumulator from the caller.

Verifying the optimization

1. Compile – run sbt compile or scalac -cp . Sum.scala in the project directory. No error should appear; if you accidentally place the annotation on the naïve version, the compiler will emit:

error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position

2. Inspect bytecode – after compilation, run javap -c Sum$$.class (the inner class name may be Sum$$ or Sum$loop$1). Look for a loop construct; you should see something like:

  Code:
     0: iconst_0
     1: istore_2
     2: aload_1
     3: invokevirtual #2  // Method scala/collection/immutable/List.isEmpty:()Z
     6: ifeq 13
     9: iload_2
    10: ireturn
    11: goto 2

The presence of a goto (or while) instead of an invokevirtual to the same method confirms tail‑call elimination.

3. Run with a large input – execute:

scala -cp target/scala-2.13/classes Sum 1000000

where Sum contains a def main(args: Array[String]): Unit = println(sumTail((1 to args(0).toInt).toList)). The program should finish quickly and print the expected sum (500000500000 for 1 000 000). If you run the same code without @tailrec (or with the naïve version), you will see a java.lang.StackOverflowError.

Limitations and when to refactor

• Only self‑recursion – @tailrec cannot verify mutual recursion or recursion hidden inside higher‑order calls like map or filter. In those cases you must rewrite the algorithm to expose the tail call or use a trampoline (scala.util.control.TailCalls).
• Try/catch interferes – any non‑tail operation after the recursive call, including exception handling, blocks optimization. Move the try inside the recursive step if you need to catch errors per iteration.
• Cross‑platform nuances – while the JVM guarantees loop generation, Scala Native and Scala.js may emit different code. When targeting those backends, inspect the generated output or run the same large‑input test to confirm no stack growth.

Takeaway

Use @tailrec as a safety net: it lets the compiler prove that a recursive method will run in constant stack space. Write the recursion with an accumulator, place the annotation on the inner helper, verify with javap and a large‑input test, and you’ll have list‑processing or tree‑traversal code that scales without the risk of a stack overflow.