Recursion and tail recursion in Scala

Recursion needs a smaller problem and a stopping point

A recursive function defines a result in terms of another call to itself. Useful recursion has a base case that returns directly and a recursive case that moves measurably closer to that base case. Without both, the function either does not compile into sensible behaviour or never terminates.

Linked structures make recursion natural. A List is either Nil or a head followed by a tail, and a tree is a node containing smaller trees. Pattern matching can make those cases visible in the same shape as the data.

Correctness is only the first concern. Every ordinary recursive call retains a stack frame until the nested call returns. A function that works on ten values may throw StackOverflowError on a sufficiently large input.

def sum(values: List[Int]): Int = values match {
  case Nil          => 0
  case head :: tail => head + sum(tail)
}

// The addition happens after sum(tail) returns, so each
// call must remain on the stack.

A tail call is the final operation

A function is tail-recursive only when the recursive call is the last operation performed by that branch. The caller has no addition, construction or other work left to do after the nested call returns, so the compiler can reuse the current stack frame.

The scala.annotation.tailrec annotation asks the compiler to verify that optimisation is possible. It turns an assumption about stack safety into a compile-time guarantee and should be used whenever a method is intentionally tail-recursive.

Tail recursion is an implementation property, not simply a function that happens to call itself near the bottom of the source. head + sum(tail), for example, still needs the current head after the recursive result arrives and is not a tail call.

import scala.annotation.tailrec

def sum(values: List[Int]): Int = {
  @tailrec
  def loop(remaining: List[Int], total: Int): Int =
    remaining match {
      case Nil          => total
      case head :: tail => loop(tail, total + head)
    }

  loop(values, 0)
}

Accumulators change when work happens

Converting a function to tail recursion usually means adding an accumulator containing the partial answer. Instead of waiting for a recursive result and then combining it, each step computes the next state before making the tail call.

Order matters. Prepending to a List is constant time, so a tail-recursive transformation often builds its result backwards and reverses once at the end. Repeatedly appending with :+ would preserve order locally but repeatedly traverse the accumulated list.

An accumulator should have a clear invariant: total is the sum of values already visited, or reversed contains the transformed prefix in reverse order. Naming that invariant makes the loop easier to test and review.

import scala.annotation.tailrec

def normalise(values: List[String]): List[String] = {
  @tailrec
  def loop(
    remaining: List[String],
    reversed: List[String]
  ): List[String] = remaining match {
    case Nil => reversed.reverse
    case head :: tail =>
      loop(tail, head.trim.toLowerCase :: reversed)
  }

  loop(values, Nil)
}

Direct tree recursion is not usually tail-recursive

A tree branch may require results from two or more recursive calls before the current node can be completed. Those calls are not in tail position, and @tailrec correctly rejects the method. Balanced trees may remain safe because their depth is small, while a deeply skewed or externally supplied tree can exhaust the stack.

Stack safety can be recovered by representing pending work as data. An explicit List can act as a work stack: take one node, add its children to the remaining work and tail-call with the updated accumulator.

This trades call-stack use for heap allocation and may change traversal order. Choose depth-first or breadth-first deliberately when order affects output, early termination or memory use.

import scala.annotation.tailrec

sealed trait Tree[+A]
case object Empty extends Tree[Nothing]
final case class Node[A](
  value: A,
  left: Tree[A],
  right: Tree[A]
) extends Tree[A]

@tailrec
def size[A](pending: List[Tree[A]], count: Int = 0): Int =
  pending match {
    case Nil => count
    case Empty :: rest => size(rest, count)
    case Node(_, left, right) :: rest =>
      size(left :: right :: rest, count + 1)
  }

Mutual recursion and effects need separate care

The compiler can optimise direct self-recursion in tail position, but mutually recursive methods do not receive the same guarantee. Two methods that call one another can still overflow even when each call appears last in its method.

Recursion across Future.flatMap callbacks also does not become safe merely because flatMap appears last. The execution model determines when callbacks run. Effect libraries such as Cats Effect provide stack-safe flatMap for effect programs, but pure recursive work performed before constructing the next effect can still overflow.

For general recursion expressed through an effect, Cats provides abstractions such as tailRecM. At application level, a collection combinator, an explicit work queue or a library traversal is often easier to understand than implementing the abstraction directly.

def unsafeLoop(value: Int): IO[Int] =
  if (value <= 0) IO.pure(0)
  else unsafeLoop(value - 1).map(_ + 1)

// The recursive call happens while building the IO value.
// Prefer a stack-safe combinator or an explicit iterative state.

Collection operations are often the better vocabulary

Many recursive list functions are already captured by map, collect, exists, find and foldLeft. These operations state the intent directly, are familiar to Scala developers and use stack-safe implementations for ordinary strict collections.

Writing the recursion yourself is justified when the data is naturally recursive, traversal needs unusual control, several pieces of state must evolve together or early termination has domain-specific rules. It can also be useful when teaching or measuring an algorithm, but production code should not make the reader rediscover a standard fold.

A fold is not automatically clearer. When its accumulator becomes a tuple of several unrelated values, a named state case class or a small @tailrec loop can expose the transition more plainly.

val total: Int = values.foldLeft(0)(_ + _)
val normalised: List[String] = values.map(_.trim.toLowerCase)
val firstInvalid: Option[String] = values.find(value => !isValid(value))

final case class State(total: BigDecimal, rejected: Vector[Payment])

val result = payments.foldLeft(State(BigDecimal(0), Vector.empty)) {
  case (state, payment) if payment.accepted =>
    state.copy(total = state.total + payment.amount)
  case (state, payment) =>
    state.copy(rejected = state.rejected :+ payment)
}

Test boundaries, not only examples

Recursive code deserves tests for the empty structure, one element, ordinary input and the largest realistic depth. Property-based tests can compare an implementation with a simpler reference or check invariants such as reversing twice returning the original list.

A @tailrec annotation proves that direct self-calls are optimised; it does not prove termination, correctness or sensible memory use. A loop can be constant-stack and infinite, or move a huge pending structure from the stack to the heap.

During review, identify the decreasing input, base case, accumulator invariant and maximum expected depth. If any of those are hard to state, the implementation is asking readers to trust more than the code demonstrates.

• Annotate intentional tail recursion with @tailrec
• Check that every recursive branch moves toward a base case
• Avoid repeated List append in accumulators
• Use an explicit work structure for deeply nested trees or graphs
• Prefer standard collection combinators when they express the operation directly
• Test empty input and realistic worst-case depth