Immutability, Recursion and Folds

Thinking without mutation

Functional code transforms immutable values instead of updating variables in place. Loops become recursion or, more often, higher-order functions: foldLeft threads an accumulator through a collection (orders.foldLeft(0L)(_ + _.totalPaise)), reduce combines elements, and scanLeft keeps intermediate results. Recursive functions on the JVM can overflow the stack for deep inputs, so write tail-recursive functions, where the recursive call is the last action, and annotate them with @tailrec: the compiler turns them into loops and reports an error if the call is not in tail position. Accumulator parameters are the usual technique. Immutable data structures are persistent: updating a Vector or Map shares most of its structure with the old version, so copies are cheap. Keep state changes at the edges of your program (I/O, databases) and keep the core logic pure, a style sometimes called "functional core, imperative shell". Local mutation inside a function is acceptable when it is invisible from outside and clearly faster.

Tail recursion and folds

@tailrec checks the recursive call is in tail position.

import scala.annotation.tailrec

// naive recursion: deep lists can overflow the stack
def sumNaive(xs: List[Long]): Long = xs match
  case Nil    => 0
  case h :: t => h + sumNaive(t)          // not a tail call: addition happens after

@tailrec
def sumAcc(xs: List[Long], acc: Long = 0): Long = xs match
  case Nil    => acc
  case h :: t => sumAcc(t, acc + h)       // tail call: compiled into a loop

def emiSchedule(principal: BigDecimal, monthlyRate: BigDecimal, emi: BigDecimal): List[BigDecimal] =
  require(emi > principal * monthlyRate, "EMI must exceed the first month's interest")
  @tailrec
  def loop(balance: BigDecimal, acc: List[BigDecimal]): List[BigDecimal] =
    if balance <= BigDecimal(0) then acc.reverse
    else
      val interest = balance * monthlyRate
      val next = (balance + interest - emi).max(BigDecimal(0))
      loop(next, next :: acc)
  loop(principal, Nil)

case class Stats(count: Int, total: Long, max: Long)

val totals = List(120000L, 30000L, 80000L)
val stats = totals.foldLeft(Stats(0, 0, Long.MinValue)) { (s, t) =>
  Stats(s.count + 1, s.total + t, s.max.max(t))
}
println(stats)                             // Stats(3,230000,120000)
println(sumAcc((1L to 100000L).toList))    // 5000050000

@tailrec is a safety check

@tailrec does not make a function tail-recursive; it makes the compiler prove that it is. If you refactor and accidentally break the tail call, compilation fails instead of production overflowing the stack.

Quick check: What does the @tailrec annotation do?

• Makes the compiler verify the recursive call is in tail position, compiling it into a loop
• Makes any recursive function fast
• Runs the function in parallel
• Caches results