Scala Tail Recursion, in depth: what the compiler rewrites, what @tailrec really does, accumulators, explicit stacks, TailCalls and stack-safe monads

The stack problem, from first principles

Every method call on the JVM pushes a frame onto the calling thread's stack. The frame holds the method's parameters, local variables and the place to return to. It is popped when the method returns. Recursion that goes n levels deep therefore holds n frames at once, and the stack has a fixed size, set per thread by the -Xss option; on HotSpot on 64-bit Linux the default is 1 MB. The overflow depth varies with frame size, which is why the bug survives small tests and appears in production with a long list.

Some runtimes reuse the current frame when a call is a function's last action. The JVM does not, so Scala does the transformation at compile time for the case it can prove safe.

What a tail call is

A call is in tail position when its result is returned directly, with no further work afterwards. In h + sumNaive(t) the call is not in tail position, because after it returns the method still has to add h. In go(t, acc + h) the call is the whole result of the branch, so nothing in the current frame is needed afterwards and the frame can be reused.

Tail position propagates through expression structure: the last expression of a block, both branches of an if, and the right-hand side of every case in a match are in tail position if the whole expression is. It does not reach into arguments of other calls, into the body of a try, or into a lambda passed somewhere else.

import scala.annotation.tailrec

// Not tail recursive: the addition happens AFTER the recursive call returns.
def sumNaive(xs: List[Long]): Long = xs match
  case Nil    => 0L
  case h :: t => h + sumNaive(t)

// Tail recursive: the recursive call is the last thing the method does.
def sum(xs: List[Long]): Long =
  @tailrec
  def go(rest: List[Long], acc: Long): Long = rest match
    case Nil    => acc
    case h :: t => go(t, acc + h)
  go(xs, 0L)

val big = List.range(0L, 1_000_000L)
// sumNaive(big)  // java.lang.StackOverflowError on a default stack
sum(big)          // 499999500000, one stack frame

The fix shown is the standard one. The pending work, the addition, moves into an extra parameter, the accumulator, so it is done before the call instead of after.

What scalac actually does

In its tail-calls phase the compiler looks for methods that call themselves in tail position. When it finds one that qualifies, it compiles the method body as a loop: the parameters become local variables, and each tail call evaluates the new argument values and then jumps back to the start of the method. The recursion runs in constant stack space, at the speed of a while loop.

// Roughly what scalac generates for go: parameters become variables, the call becomes a jump.
def go(rest0: List[Long], acc0: Long): Long =
  var rest = rest0
  var acc  = acc0
  while true do
    rest match
      case Nil    => return acc
      case h :: t =>
        acc = acc + h      // evaluate the new arguments first...
        rest = t           // ...then rebind and loop
  throw new AssertionError("unreachable")

Three conditions must hold. The call must be to the same method, not another method that happens to call back. It must be in tail position. And the method must not be overridable, because a call to an overridable method might dispatch to a subclass's version at run time, and replacing it with a jump would change the program's meaning. So the method must be final, private, defined in an object, or a local def inside another method.

Now the point most readers arrive with backwards: the annotation does not cause the optimisation. scalac rewrites every qualifying self tail call whether or not it is annotated. What @tailrec adds is a guarantee. If the annotated method cannot be rewritten, compilation fails with an error explaining why. Without it, a refactor that breaks tail position compiles silently. Annotate every method you rely on being stack safe.

Why a call fails to qualify

The compiler's error messages differ between Scala 2 and Scala 3, but the causes reduce to a short list. Each is shown below with its fix.

import scala.annotation.tailrec

class Counter:
  // Fails: public method of a class can be overridden, so the call may not be to this body.
  @tailrec def countDown(n: Int): Int = if n == 0 then 0 else countDown(n - 1)

  // Works: final (or private, or defined in an object, or a local def) cannot be overridden.
  @tailrec final def countDownOk(n: Int): Int = if n == 0 then 0 else countDownOk(n - 1)

object Examples:
  // Fails: the call is inside a try block, whose handler must stay active.
  @tailrec def retry(n: Int): Int =
    try { if n == 0 then 0 else retry(n - 1) }
    catch { case _: Exception => -1 }

  // Fails: the result is used by a further operation (factorial's multiplication).
  @tailrec def fact(n: Int): BigInt = if n <= 1 then 1 else n * fact(n - 1)

  // Works: move the pending work into an accumulator.
  @tailrec def factAcc(n: Int, acc: BigInt = 1): BigInt =
    if n <= 1 then acc else factAcc(n - 1, acc * n)

Trees and other non-linear recursion

A function over a binary tree makes two recursive calls, and only one can be last. An accumulator alone cannot fix that. The general technique is to make the stack explicit: keep the work you have not done yet in a List on the heap, and loop over it.

enum Tree:
  case Leaf(value: Int)
  case Node(left: Tree, right: Tree)

import Tree.*

// Two recursive calls cannot both be in tail position. Keep the pending work in a List instead.
def sumTree(root: Tree): Long =
  @annotation.tailrec
  def loop(stack: List[Tree], acc: Long): Long = stack match
    case Nil                 => acc
    case Leaf(v) :: rest     => loop(rest, acc + v)
    case Node(l, r) :: rest  => loop(l :: r :: rest, acc)
  loop(List(root), 0L)

A leaf adds to the accumulator; a node pushes its children; the method is self tail recursive. The same pattern handles graph traversal and directory walks. Before writing a loop at all, check whether a standard combinator already does it: foldLeft on List is implemented as a loop, and folds are covered in fold, map and filter.

Mutual recursion with TailCalls

When two functions call each other the compiler's rewrite does not apply, because neither method calls itself. The standard library's answer is a trampoline in scala.util.control.TailCalls. Instead of making the call, each function returns a description of it: done(value) for a finished result, tailcall(f(x)) for 'call f next'. The .result method runs a loop that keeps evaluating descriptions until it reaches a done value. The stack stays flat because each step returns to the loop before the next begins.

import scala.util.control.TailCalls.*

// Mutual recursion: neither method calls itself, so scalac cannot turn it into a loop.
def isEven(n: Int): TailRec[Boolean] = if n == 0 then done(true)  else tailcall(isOdd(n - 1))
def isOdd(n: Int): TailRec[Boolean]  = if n == 0 then done(false) else tailcall(isEven(n - 1))

isEven(1_000_001).result   // false; runs on the heap, one small object per step

The cost is a heap allocation per step, so a trampoline is slower than a compiled loop. Where you can, merge the functions into one with a state parameter instead, which turns mutual recursion back into self recursion.

Stack safety in functional libraries

Code written against Cats or Cats Effect recurses through flatMap rather than direct calls, and the libraries are designed to keep that stack safe. Cats' Monad type class, through FlatMap, requires tailRecM, which expresses a loop as a function from state to Either: Left means continue with a new state, Right means finish. Lawful instances implement it without growing the stack. Eval trampolines ordinary recursive definitions through Eval.defer, and recursion through flatMap in Cats Effect IO is stack safe because the runtime interprets IO as data rather than as nested calls.

import cats.{Eval, Monad}
import cats.effect.IO

// tailRecM: Left means "continue with this state", Right means "finished with this value".
def collatzSteps[F[_]: Monad](n: Long): F[Int] =
  Monad[F].tailRecM((n, 0)) { case (x, steps) =>
    Monad[F].pure(
      if x == 1 then Right(steps)
      else Left((if x % 2 == 0 then x / 2 else 3 * x + 1, steps + 1))
    )
  }

// Eval.defer trampolines a recursive definition that is not tail recursive.
def evalSum(xs: List[Long]): Eval[Long] = xs match
  case Nil    => Eval.now(0L)
  case h :: t => Eval.defer(evalSum(t)).map(_ + h)

// Recursion through flatMap in Cats Effect IO is stack safe.
def countdown(n: Int): IO[Unit] = if n == 0 then IO.unit else IO.unit.flatMap(_ => countdown(n - 1))

A hand-written monad instance can break the guarantee if its tailRecM simply calls flatMap recursively. See Cats Effect for the runtime, and free monads for how interpreting programs as data gives this property.

Performance and choosing a technique

Do not convert every recursive function by reflex. A balanced tree of a billion nodes is only about thirty levels deep. Convert when depth tracks input size. For lazily built sequences, LazyList is another way to avoid materialising deep structures, and the costs of List operations are described in Scala List.

Testing for stack safety

A stack-safety bug only shows with large inputs, so test with large inputs. A million elements overflows a default stack for any linear non-tail recursion, and runs in milliseconds for a correct loop. For tree code, include a degenerate tree that is really a long list.

class StackSafetySpec extends munit.FunSuite:
  // Deep enough to overflow a default stack if the code is not stack safe.
  val n = 1_000_000

  test("sum is stack safe") {
    assertEquals(sum(List.fill(n)(1L)), n.toLong)
  }

  test("sumTree handles a degenerate, list-shaped tree") {
    val deep = (1 to n).foldLeft(Tree.Leaf(0): Tree)((t, i) => Tree.Node(t, Tree.Leaf(1)))
    assertEquals(sumTree(deep), n.toLong)
  }

Do not hide the problem by raising -Xss. A bigger stack moves the failure to a bigger input and makes every thread more expensive. If a third-party algorithm needs deep recursion, run it on a dedicated thread created with an explicit stack size.

What to do next

1. Search your code for recursive functions whose depth grows with input size, and add a million-element test for each.
2. Annotate every function you rely on being stack safe with @tailrec, so a refactor that breaks it fails the build.
3. Rewrite linear recursion with an accumulator and a local go helper; make class methods final or private if they recurse.
4. Move try blocks out of recursive paths, using Try or Either and matching on the result.
5. Convert tree and graph recursion over unbounded inputs to an explicit work list.
6. Use TailCalls for mutual recursion, or merge the functions into one with a state parameter.
7. In Cats code, express loops with tailRecM and check any hand-written Monad instance with the stack-safety laws in cats-laws.