Scala Tail Recursion

Tail recursion is a special form of recursion where the recursive call is the very last action of the function — nothing else happens after it. Scala's compiler detects tail-recursive functions and converts them into efficient loops under the hood, eliminating the risk of stack overflow for large inputs.

Regular vs Tail Recursion

// Regular recursion — NOT tail recursive
// After factorial(n-1) returns, multiplication still happens
def factorial(n: Int): Long =
  if n <= 1 then 1L
  else n * factorial(n - 1)    // n * ... runs AFTER recursive call

// Tail recursive — uses an accumulator
def factorialTail(n: Int, acc: Long = 1L): Long =
  if n <= 1 then acc                      // base: return accumulator
  else factorialTail(n - 1, n * acc)     // tail call: nothing after this

Regular factorial(5):
  5 * factorial(4)
      4 * factorial(3)
          3 * factorial(2)
              2 * factorial(1)
              ← unwinds back: 2 * 1 = 2, 3*2=6, 4*6=24, 5*24=120
  STACK: holds 5 frames simultaneously

Tail factorial(5, acc=1):
  factorialTail(4, 5*1=5)
  factorialTail(3, 4*5=20)
  factorialTail(2, 3*20=60)
  factorialTail(1, 2*60=120) → returns 120
  STACK: only 1 frame at a time (compiler converts to loop)

The @tailrec Annotation

Add @tailrec to ask the compiler to verify that your function is truly tail recursive. If it is not, the compiler gives an error:

import scala.annotation.tailrec

@tailrec
def factorialTail(n: Int, acc: Long = 1L): Long =
  if n <= 1 then acc
  else factorialTail(n - 1, n * acc)

println(factorialTail(10))    // 3628800
println(factorialTail(20))    // 2432902008176640000L

// This runs for 100,000 without stack overflow:
@tailrec
def countDown(n: Int): Unit =
  if n > 0 then countDown(n - 1)

countDown(1000000)   // no problem!

Tail Recursive Sum

import scala.annotation.tailrec

@tailrec
def sumTo(n: Int, acc: Int = 0): Int =
  if n <= 0 then acc
  else sumTo(n - 1, acc + n)

println(sumTo(100))     // 5050
println(sumTo(100000))  // runs fine

Tail Recursive List Operations

import scala.annotation.tailrec

@tailrec
def sumList(nums: List[Int], acc: Int = 0): Int =
  nums match
    case Nil          => acc
    case head :: tail => sumList(tail, acc + head)

@tailrec
def reverseList[A](list: List[A], acc: List[A] = Nil): List[A] =
  list match
    case Nil          => acc
    case head :: tail => reverseList(tail, head :: acc)

println(sumList(List(1, 2, 3, 4, 5)))            // 15
println(reverseList(List("a", "b", "c", "d")))   // List(d, c, b, a)

reverseList(List(1,2,3), acc=Nil)
→ reverseList(List(2,3), acc=1::Nil = List(1))
→ reverseList(List(3), acc=2::List(1) = List(2,1))
→ reverseList(Nil, acc=3::List(2,1) = List(3,2,1))
→ returns List(3,2,1)

Accumulator Pattern

Converting a regular recursive function to tail recursive almost always involves adding an accumulator parameter that collects the result:

// Step 1: Identify what is computed on the way back up the stack
// factorial builds: n * (n-1) * ... * 1

// Step 2: Move that computation into an accumulator
// factorialTail carries the partial product in acc

// General pattern:
// def recFunc(input, acc = initialValue): Result =
//   if baseCase then acc
//   else recFunc(smallerInput, updateAcc)

Tail Recursive Fibonacci (Efficient)

import scala.annotation.tailrec

@tailrec
def fibonacci(n: Int, a: Int = 0, b: Int = 1): Int =
  if n == 0 then a
  else fibonacci(n - 1, b, a + b)

for i <- 0 to 10 do print(s"${fibonacci(i)} ")
// 0 1 1 2 3 5 8 13 21 34 55

This version uses two accumulators: a and b representing the previous two Fibonacci numbers. It runs in O(n) time and O(1) stack space — far better than the naive recursive version.

When @tailrec Reports an Error

import scala.annotation.tailrec

// This FAILS @tailrec — multiplication happens after the call
@tailrec
def badFactorial(n: Int): Long =
  if n <= 1 then 1L
  else n * badFactorial(n - 1)    // Error: not in tail position

// Error: could not optimize @tailrec annotated method:
//   it contains a recursive call not in tail position

The annotation catches your mistake at compile time. Without it, the function compiles but crashes at runtime for large inputs.

Trampoline for Mutual Recursion

Two functions calling each other (mutual recursion) cannot both be @tailrec. Use Scala's TailCalls utility for this pattern:

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

println(isEven(100000).result)   // true  — no stack overflow
println(isOdd(99999).result)     // true

Summary: Regular vs Tail Recursion

Feature                Regular Recursion      Tail Recursion
─────────────────────  ────────────────────   ──────────────────────
Stack frames used      One per call           One total (reused)
Risk of overflow       Yes (large inputs)     No
@tailrec annotation    Not applicable         Use to verify
Needs accumulator      No                     Usually yes
Compiler optimization  None                   Converted to loop

Tail recursion gives you the clarity of recursive code with the performance of a loop. Always annotate recursive functions with @tailrec and use an accumulator to ensure they are stack-safe for production use.