Lesson 12 / 25
Immutability, Recursion and Folds
Replace loops and mutation with recursion, tail calls and folds.
By Rahul Agarwal · 15 years in web development
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
Answer
Makes the compiler verify the recursive call is in tail position, compiling it into a loop — It guarantees tail-call optimisation or a compile error.