Learn

Functional code prefers recursion over imperative loops. Scala has two kinds: regular recursion (limited by stack) and tail recursion (optimized by the compiler into a loop).

Regular recursion

def factorial(n: Int): Int = {
    if (n <= 1) 1
    else n * factorial(n - 1)
}

factorial(5)        // 120

This works for small n. Try factorial(10000) and you get a StackOverflowError — every recursive call adds a stack frame.

Tail recursion

A recursive call is in tail position if it's the LAST thing the function does:

import scala.annotation.tailrec

@tailrec
def factorial(n: Int, acc: Int = 1): Int = {
    if (n <= 1) acc
    else factorial(n - 1, acc * n)        // tail position
}

factorial(10000)    // works — no stack overflow

The @tailrec annotation tells the compiler to verify the call is tail-recursive — and to optimize it into a loop. Without @tailrec and a tail call, the compiler still attempts the optimization but doesn't error if not possible.

Why this works: at the recursive call, the current frame's work is done. The compiler can REUSE the stack frame for the next call instead of stacking a new one. Effectively transforms recursion into iteration.

Accumulator pattern

The trick to making non-tail-recursive functions tail-recursive: introduce an accumulator parameter:

// Not tail-recursive (multiplies AFTER recursive call returns)
def sum(list: List[Int]): Int = list match {
    case Nil => 0
    case x :: xs => x + sum(xs)             // x + ... is the last operation, NOT the call
}

// Tail-recursive with accumulator
@tailrec
def sumTail(list: List[Int], acc: Int = 0): Int = list match {
    case Nil => acc
    case x :: xs => sumTail(xs, acc + x)    // call IS the last thing
}

The accumulator carries the running result. By the time you hit the base case, acc holds the answer.

When recursion fits

• Tree/list traversal
• Divide-and-conquer (mergesort, binary search)
• Sequence generation
• Pattern matching on recursive data structures

When NOT to recurse

• Simple loops over indices — for (i <- 0 until n) is clearer
• Stateful iteration with mutable state — recursion + state is awkward
• Performance-critical hot paths where the JIT might not specialize

In Scala, prefer collection methods (map, foldLeft, reduce) when applicable — they're tail-recursive internally and read better.

Mutual recursion

Mutually recursive functions (A calls B, B calls A) cannot be @tailrec-optimized:

def isEven(n: Int): Boolean = if (n == 0) true else isOdd(n - 1)
def isOdd(n: Int): Boolean = if (n == 0) false else isEven(n - 1)

For mutual recursion at scale, use trampolining via scala.util.control.TailCalls.

Common mistakes

• @tailrec on a non-tail call — compile error. Helpful for catching when your refactor accidentally introduces non-tail calls.
• Adding accumulator but still wrapping — n * factorial(n-1) is not tail. The CALL must be the last operation, not the multiplication.
• Stack overflow on large inputs — sign that the function isn't tail-recursive (or you needed iteration).
• Confusing tail recursion with general recursion — most natural-looking recursion is NOT tail-recursive. The accumulator pattern is the conversion.