Recursion & Tail Calls

This content was generated with the assistance of AI and should be verified against the official documentation before being relied on in production.

The reference material consulted while preparing these pages is listed in the section bibliography.

This page is written against Scala 3.10 (3.10.0, 2026-10-12) and every example was run with Scala CLI and Scala 3.10.0 on JDK 26 on 2026-10-15 (the examples were not re-run on 3.9 or 3.3). Nothing used here is newer than Scala 3.0, so it applies to the 3.3 LTS and 3.9 LTS lines as well. Where an observed behaviour depends on the JVM (the depth at which a stack overflows), the page says so.

Functional Scala code replaces loops with recursion: a method that calls itself on a smaller part of the input. The JVM gives every call a stack frame and the stack is finite, so a recursion that is deep enough ends in a StackOverflowError. Scala answers with tail-call optimisation for self-recursive methods, the @tailrec annotation that turns a silent optimisation into a compile-time guarantee, and a library trampoline for the cases the compiler cannot handle. The method basics are in Methods & Parameters; the data types used below are explained in Enums and Pattern Matching.

The examples use the trailhead scenario of this section: a toolkit that plans hikes on a network of mountain trails.

Recursion over data

A recursive method has one case per shape of the data: the base case that ends the recursion, and the recursive case that calls itself on a smaller piece. Pattern matching expresses exactly that shape. A list is either Nil or a head followed by a tail, and an enum such as a route that is either a leg or a fork is a tree.

//> using scala 3.10.0

enum Route:
  case Leg(km: Double)
  case Fork(left: Route, right: Route)

import Route.*

def totalKm(r: Route): Double = r match
  case Leg(km)       => km
  case Fork(a, b)    => totalKm(a) + totalKm(b)

def lengthOf[A](xs: List[A]): Int = xs match
  case Nil       => 0
  case _ :: rest => 1 + lengthOf(rest)

@main def r1(): Unit =
  val r = Fork(Leg(2.5), Fork(Leg(1.0), Leg(4.0)))
  println(totalKm(r))
  println(lengthOf(List("a", "b", "c")))
  try println(lengthOf(List.range(0, 1_000_000)))
  catch case e: StackOverflowError => println(s"StackOverflowError: ${e.getClass.getName}")

7.5
3
StackOverflowError: java.lang.StackOverflowError

Source: Scala 3 Book: Writing your own map method

totalKm recurses on a tree, and its depth is the depth of the tree, which is small for any realistic route, so plain recursion is fine. lengthOf recurses once per element, and the list of a million elements overflowed the stack on this machine (JDK 26, default thread stack size). The exact depth depends on the JVM, the stack size (-Xss) and the frame size, so no fixed depth can be relied on. The recursive call in 1 + lengthOf(rest) is not the last thing the method does: it must come back and add 1, so the frame has to stay.

A recursive method needs an explicit result type, as the compiler cannot infer a type from a body that refers to itself.

Tail calls and accumulators

A call is in tail position when it is the last thing the method does, so its result is returned unchanged. A self-call in tail position needs no new frame: the compiler rewrites the method into a loop. The standard way to reach tail position is an accumulator, an extra parameter that carries the result so far, usually hidden in a local helper.

//> using scala 3.10.0
import scala.annotation.tailrec

def lengthOf[A](xs: List[A]): Int =
  @tailrec def go(rest: List[A], acc: Int): Int = rest match
    case Nil       => acc
    case _ :: tail => go(tail, acc + 1)
  go(xs, 0)

@tailrec
def gcd(a: Int, b: Int): Int = if b == 0 then a else gcd(b, a % b)

@main def r2(): Unit =
  println(lengthOf(List.range(0, 1_000_000)))
  println(gcd(84, 36))

1000000
12

Source: Scala API: tailrec and Scala Glossary: tail recursive

The same million-element list now works: go is rewritten into a loop. The accumulator also changes the order in which the work happens: go adds to the result on the way down, while the naive version adds on the way up. For an operation that builds a list this means the result comes out reversed, and the usual fix is a final acc.reverse.

What `@tailrec` guarantees

scala.annotation.tailrec does not cause the optimisation. The compiler optimises self tail calls whether or not the annotation is present. What the annotation adds is a promise: if the method cannot be compiled into a loop, that is a compile error, not a silent fall-back to a stack overflow at run time. Always annotate a method that you rely on to run in constant stack.

//> using scala 3.10.0
import scala.annotation.tailrec

@tailrec
def factorial(n: Int): BigInt =
  if n <= 1 then 1 else n * factorial(n - 1)

@main def r3(): Unit = println(factorial(5))

[error] ./r3.scala:6:29
[error] Cannot rewrite recursive call: it is not in tail position
[error]   if n <= 1 then 1 else n * factorial(n - 1)
[error]                             ^^^^^^^^^^^^^^^^
Compilation failed

Source: Scala API: tailrec

The compiler points at the call that is not in tail position (n * factorial(n - 1), because of the pending multiplication). The cure is an accumulator: def go(n: Int, acc: BigInt): BigInt.

The other situations in which @tailrec is rejected, with the compiler messages:

//> using scala 3.10.0
import scala.annotation.tailrec

class Walker:
  @tailrec
  final def count(n: Int): Int = if n == 0 then 0 else count(n - 1)
  @tailrec
  def countOpen(n: Int): Int = if n == 0 then 0 else countOpen(n - 1)

@main def r4(): Unit = println(Walker().count(10))

[error] ./r4.scala:8:7
[error] TailRec optimisation not applicable, method countOpen is neither private nor final so can be overridden
[error]   def countOpen(n: Int): Int = if n == 0 then 0 else countOpen(n - 1)
[error]       ^
Compilation failed

Source: Scala API: tailrec

//> using scala 3.10.0
import scala.annotation.tailrec

@tailrec
def safe(n: Int): Int =
  try if n == 0 then 0 else safe(n - 1)
  catch case _: Exception => -1

@tailrec
def a(n: Int): Boolean = if n == 0 then true else b(n - 1)
def b(n: Int): Boolean = if n == 0 then false else a(n - 1)

@main def r5(): Unit = println(safe(3))

[error] ./r5.scala:6:29
[error] Cannot rewrite recursive call: it is not in tail position
[error]   try if n == 0 then 0 else safe(n - 1)
[error]                             ^^^^^^^^^^^
[error] ./r5.scala:10:5
[error] TailRec optimisation not applicable, method a contains no recursive calls
[error]   def a(n: Int): Boolean = if n == 0 then true else b(n - 1)
[error]     ^
Compilation failed

Source: Scala API: tailrec

The rules these three errors encode:

The method must not be overridable. A method in a class has to be final or private (or be in an object, or a local def), because a subclass could replace the callee. count is accepted, countOpen is not.
A call inside try is never a tail call, because the catch and finally blocks must still run in the frame.
Only direct self-calls count. Mutual recursion (a calls b calls a) is not rewritten; the annotation reports contains no recursive calls because a does not call itself. The next section handles mutual recursion.
Only the last call counts. A call whose result is combined with something, or that is wrapped by a lambda, is not in tail position.

Without the annotation the same methods compile silently. The next example calls three unannotated self-recursive methods five million times deep: the top-level method and the one in an object ran fine, and the one in an open class overflowed.

//> using scala 3.10.0
def countDown(n: Int): Int = if n == 0 then 0 else countDown(n - 1)
object Cnt:
  def open(n: Int): Int = if n == 0 then 0 else open(n - 1)
class K:
  def open(n: Int): Int = if n == 0 then 0 else open(n - 1)
@main def r8(): Unit =
  println(countDown(5_000_000))
  println(Cnt.open(5_000_000))
  try println(K().open(5_000_000)) catch case _: StackOverflowError => println("K.open: StackOverflowError")

0
0
K.open: StackOverflowError

Source: Scala API: tailrec

Java and Kotlin differ here. The JVM itself does not perform tail-call elimination, and javac never rewrites recursion into a loop; Kotlin’s tailrec modifier is the counterpart of Scala’s annotation, with the same restriction to direct self-calls.

Folds as recursion schemes

Most recursions over a collection have one of two shapes, and the standard library already implements them. A left fold walks the list from the head, passing an accumulator, which is exactly the tail-recursive go above. A right fold combines each element with the result for the rest of the list, which is the non-tail recursion of sumRec below.

//> using scala 3.10.0
import scala.annotation.tailrec

def myMap[A, B](xs: List[A])(f: A => B): List[B] = xs match
  case Nil     => Nil
  case h :: t  => f(h) :: myMap(t)(f)

def myMapSafe[A, B](xs: List[A])(f: A => B): List[B] =
  @tailrec def go(rest: List[A], acc: List[B]): List[B] = rest match
    case Nil    => acc.reverse
    case h :: t => go(t, f(h) :: acc)
  go(xs, Nil)

@main def r7(): Unit =
  val xs = List(1, 2, 3, 4)
  println(myMap(xs)(_ * 2))
  println(myMapSafe(xs)(_ * 2))
  println(xs.foldLeft(0)(_ + _))
  println(xs.foldRight(0)(_ + _))
  println(xs.foldLeft(List.empty[Int])((acc, x) => x :: acc))
  println(xs.foldRight(List.empty[Int])((x, acc) => x :: acc))
  val big = List.range(0, 1_000_000)
  println(big.foldLeft(0L)(_ + _))
  println(big.foldRight(0L)(_ + _))
  println(myMapSafe(big)(_ + 1).size)
  try println(myMap(big)(_ + 1).size)
  catch case _: StackOverflowError => println("myMap: StackOverflowError")

List(2, 4, 6, 8)
List(2, 4, 6, 8)
10
10
List(4, 3, 2, 1)
List(1, 2, 3, 4)
499999500000
499999500000
1000000
myMap: StackOverflowError

Source: Scala 3 Book: Writing your own map method

What to take from it:

foldLeft(z)(f) is the accumulator pattern, and foldRight(z)(f) is the "combine on the way back" pattern; foldLeft with x :: acc reverses the list and foldRight keeps the order.
The hand-written myMap overflowed on a million elements, the accumulator version did not, and big.foldRight on a List did not either: the standard List.foldRight does not recurse deeply (in 2.13 it folds the reversed list from the left), so the cost of "right" is an extra pass, not an overflow. This is a property of List, not of right folds in general; do not assume it for a hand-written recursion or a lazy structure.
Prefer a fold, map, flatMap or collect to writing a recursion by hand when the shape fits. A hand-written tail-recursive go is for the cases the combinators do not cover, such as loops with several accumulators or early exit.

Mutual recursion and trampolining

When two methods call each other, or a method recurses in non-tail positions that cannot be rewritten, the compiler cannot help. scala.util.control.TailCalls implements a trampoline: instead of calling the next step directly, a step returns a description of the call (tailcall(...)) or a final value (done(...)), and .result runs the steps in a loop on a single stack frame.

//> using scala 3.10.0
import scala.util.control.TailCalls.*

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))

def plainEven(n: Int): Boolean = if n == 0 then true else plainOdd(n - 1)
def plainOdd(n: Int): Boolean = if n == 0 then false else plainEven(n - 1)

// non-tail recursion, still stack safe, through flatMap
def fib(n: Int): TailRec[BigInt] =
  if n < 2 then done(n)
  else tailcall(fib(n - 1)).flatMap(a => tailcall(fib(n - 2)).map(b => a + b))

@main def r6(): Unit =
  println(isEven(1_000_001).result)
  println(fib(20).result)
  try println(plainEven(1_000_001))
  catch case _: StackOverflowError => println("plainEven: StackOverflowError")

false
6765
plainEven: StackOverflowError

Source: Scala API: TailCalls

TailRec[A] has map and flatMap, which is what lets even a non-tail recursion be written in a stack safe way. The fib above is the naive exponential algorithm, used only to show the shape; the same pattern makes a deep non-tail recursion safe:

//> using scala 3.10.0
import scala.util.control.TailCalls.*
def fact(n: Int): TailRec[BigInt] =
  if n <= 1 then done(1) else tailcall(fact(n - 1)).map(_ * n)
@main def r9(): Unit =
  println(fact(5).result)
  println(fact(20_000).result.bitLength)

120
256909

Source: Scala API: TailCalls

The price of the trampoline is an allocation for every step, so it is slower than a loop. Use it when mutual or non-tail recursion cannot be restructured; use an accumulator and @tailrec when it can. Libraries such as Cats provide a similar stack-safe monad (Eval); it is not part of the standard library.

Pitfalls

Forgetting @tailrec. The optimisation can silently stop applying when the method stops being final, gains a try, or when someone wraps the self-call in an expression. The annotation turns that into a compile error.
The accumulator reverses. A tail-recursive builder that prepends to a list produces the elements in reverse order; call reverse at the end, or use a ListBuffer, or a fold.
@tailrec on a method that calls another method that calls back is rejected (contains no recursive calls); trampoline it or merge the two methods.
Stack depth is not a fixed number. Do not hard-code "safe up to N" thresholds; the stack size and frame size vary across JVMs, flags and machines.
Deep recursion on trees: a balanced tree has logarithmic depth and is fine; a degenerate (list-shaped) tree is not. Treat the shape of the input as part of the contract.

Where the books are outdated

The Scala 3 Book’s "Writing your own map method" chapter shows recursive map over a List, but does not mention stack depth; the stack overflow in the example above is the practical limit of the pattern it teaches.
Scala 2 books model Route with a sealed trait and case classes; in Scala 3 an enum is the idiomatic form.
Material from Scala 2 describes @tailrec identically; the annotation and the TailCalls object are unchanged.

Recursion & Tail Calls

Recursion over data

Tail calls and accumulators

What @tailrec guarantees

Folds as recursion schemes

Mutual recursion and trampolining

Pitfalls

Where the books are outdated

References

What `@tailrec` guarantees