# Immutability, Recursion and Folds — Scala

Source: https://www.geekswithgeeks.com/en/scala/p-recursion

> Replace loops and mutation with recursion, tail calls 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.

```scala
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.

**Quiz:** What does the @tailrec annotation do?

- [x] 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.