Using @tailrec in Scala to Guarantee Stack‑Safe Recursion

The Problem: Accidental Stack Overflows

When writing recursive algorithms in Scala it is easy to forget whether the recursive call is in tail position. A non‑tail‑recursive method builds up a stack frame for each call; with large inputs (e.g., computing factorial of 10 000) the JVM throws a StackOverflowError. Detecting the mistake at runtime is costly, so a compile‑time guard is preferable.

How @tailrec Works

The @tailrec annotation, available since Scala 2.10 and unchanged in Scala 3, is a compile‑time check. If the annotated method is not tail‑recursive the compiler emits an error and refuses to compile. When the check succeeds, the Scala compiler rewrites the recursion into a jump (a goto‑like bytecode instruction), yielding constant‑stack execution equivalent to a while loop.

The annotation can only be applied to methods that are final, private, or defined in an object or trait. This restriction prevents a subclass from overriding the method and changing the tail‑call position after compilation.

Worked Example: Factorial with an Accumulator

Below is a naïve recursive factorial that is not tail‑recursive:

def factorial(n: Int): Int = {
  if (n <= 1) 1
  else n * factorial(n - 1) // multiplication after the recursive call
}

Adding @tailrec to this version fails to compile:

import scala.annotation.tailrec

@tailrec
def factorialBad(n: Int): Int = {
  if (n <= 1) 1
  else n * factorialBad(n - 1) // error: not tail‑recursive
}

The compiler reports:

could not optimize @tailrec annotated method: it is not tail‑recursive

To satisfy the annotation we introduce an accumulator that carries the intermediate result, making the recursive call the last operation:

import scala.annotation.tailrec

@tailrec
def factorialTailRec(n: Int, acc: Int = 1): Int = {
  if (n <= 1) acc
  else factorialTailRec(n - 1, n * acc)
}

To use it from call‑site code you typically expose a wrapper:

def factorial(n: Int): Int = factorialTailRec(n)

Verification Steps

1. Save the above code in a file Factorial.scala.
2. Compile with scalac Factorial.scala (requires Scala 2.13+ or Scala 3). The command should succeed with no errors.
3. Inspect the generated bytecode: javap -c Factorial.class. Look for a label and a goto instruction that replaces the recursive call – this indicates the loop‑like transformation.
4. Run a test with a large input, e.g., scala -cp . Factorial 20000 (assuming you add a main that prints the result). The program should finish without a StackOverflowError.
5. Change the method to be non‑tail‑recursive (remove the accumulator) and recompile; you should see the error described above.

Trade‑offs and Limitations

• Stack safety only. The annotation guarantees no stack growth but does not promise faster execution. Boxing of primitive values or closure allocation can make the tail‑recursive version slower than an explicit while loop.
• Refactoring effort. Converting a non‑tail‑recursive algorithm often requires adding accumulators or re‑thinking the control flow, which can reduce readability for complex recursions (e.g., tree traversals).
• Visibility restrictions. Because the method must be final, private, or in an object/trait, you cannot annotate a protected method in a class that is meant to be overridden.

Actionable Checklist

1. Identify a recursive method that risks stack overflow.
2. Attempt to add @tailrec; if the compiler rejects it, refactor to make the recursive call the last operation (commonly via an accumulator).
3. Verify compilation succeeds and inspect bytecode for a loop‑like pattern.
4. Run a stress test with a large input to confirm absence of StackOverflowError.
5. If performance profiling shows the tail‑recursive version is a bottleneck, consider rewriting the algorithm as an explicit while loop while preserving functional clarity.