Tail Recursion and Performance

Tail recursion

Deep recursion can overflow the stack. A tail-recursive method — where the recursive call is the very last thing done — is compiled into a loop:

import scala.annotation.tailrec

def sumNaive(xs: List[Long]): Long = xs match
  case Nil          => 0
  case head :: tail => head + sumNaive(tail)

@tailrec
def sumTail(xs: List[Long], acc: Long = 0): Long = xs match
  case Nil          => acc
  case head :: tail => sumTail(tail, acc + head)

@main def recursion(): Unit =
  val big = List.range(1L, 1_000_001L)
  println(sumTail(big))
  try println(sumNaive(big))
  catch case _: StackOverflowError => println("stack overflow!")

500000500000
stack overflow!

sumNaive still has to add head after the recursive call returns, so every call needs a stack frame. sumTail carries the running total in an accumulator, so nothing is left to do after the call.

@tailrec makes the compiler verify the method is tail-recursive:

import scala.annotation.tailrec

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

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

-- Error: Main.scala:5:37 ------------------------------------------------------
5 |  if n <= 1 then 1 else n * factorial(n - 1)
  |                            ^^^^^^^^^^^^^^^^
  |                 Cannot rewrite recursive call: it is not in tail position
1 error found

Performance tips

• Choose the right collection — Vector or ArrayBuffer for indexed access, List for prepending and recursion, Set/Map for lookups, Array for primitive-heavy number crunching.
• Avoid intermediate collections in long chains over big data — use .view, iterator, or a single foldLeft.
• Boxing — generic code stores Ints as objects. Array[Int] and specialized code avoid it in hot loops.
• Local mutation is fine in hot paths, hidden behind a pure interface.
• Measure with JMH (sbt-jmh), not ad-hoc timing: the JVM's just-in-time compiler needs warm-up, and naive benchmarks mislead.

@main def viewsVsStrict(): Unit =
  val data = (1 to 5_000_000).toVector
  val strict = data.map(_ * 2L).filter(_ % 3 == 0).map(_ + 1).sum
  val lazyView = data.view.map(_ * 2L).filter(_ % 3 == 0).map(_ + 1).sum
  val oneFold = data.foldLeft(0L)((acc, n) =>
    val d = n * 2L
    if d % 3 == 0 then acc + d + 1 else acc)
  println(strict)
  println(strict == lazyView && lazyView == oneFold)

8333333333332
true

All three compute the same result; the view and the fold avoid building two 5-million-element intermediate vectors. (The numbers are multiplied by 2L so the sum is a Long — an Int would silently overflow past about 2.1 billion.)