Recursion and persistent structures

Lesson 11 gave us typed failure — Option, Try, and Either — and a way to sequence fallible steps without null or exceptions. But every example so far has quietly leaned on library methods to walk over data. This lesson opens the box: how do you iterate at all when you have no var to increment? The answer is recursion, the FP loop. And recursion forces us back to the one worry Lesson 03 left dangling — "if data never changes in place, do I copy everything on every update?" The same chapter that teaches recursion answers it: persistent data structures share their unchanged parts, so an immutable update is cheap, not wasteful.

1 · Recursion is the FP loop

A while loop is built from mutation. var i = 0; while (i < n) { …; i = i + 1 } works only because i means a different value each pass — exactly the changing-state we spent Lesson 03 learning to avoid. Take away var and the loop has nothing to advance. So FP iterates a different way: a function calls itself on a smaller piece of the problem until there is nothing left.

Our running data shape is the cons-list — Scala's List. It is defined recursively: a list is either Nil (empty) or a head element followed by a tail list, written head :: tail. Because the data is defined by cases, the function over it is too. This mirror is called structural recursion: one branch per shape — a base case for Nil and a recursive case for head :: tail that does a little work and recurses on the strictly-smaller tail.

def length[A](xs: List[A]): Int = xs match {
  case Nil       => 0                    // base case: empty list has length 0
  case _ :: tail => 1 + length(tail)     // recursive case: 1 + length of the rest
}

def sum(xs: List[Int]): Int = xs match {
  case Nil       => 0                    // base case: identity for +
  case h :: tail => h + sum(tail)        // recursive case: head plus sum of rest
}

Look closely at sum: a base value (0) and a combine step (h + …). That is exactly a fold from Lesson 09 — xs.foldRight(0)(_ + _). A fold is structural recursion packaged as a higher-order function: you hand it the base case and the combine function, and it supplies the recursion. Whenever you find yourself writing this pattern by hand, a fold usually says it more clearly.

2 · The stack problem

Each unfinished call must be remembered: h + sum(tail) cannot finish until sum(tail) returns, so the runtime parks a stack frame holding h and "add when the rest comes back." For a list of length n, that is n parked frames before any addition happens. The call stack is a fixed, small region of memory; pile up enough frames and you get a StackOverflowError — typically somewhere in the tens of thousands of elements. A naive recursive walk is correct but not safe for large input.

3 · Tail recursion and the accumulator

The fix: arrange the recursion so that the recursive call is the last thing the function does — there is no pending + waiting on its return. Such a call is tail-recursive. When the recursive call is in tail position, the current frame has no remaining work, so the runtime can reuse it instead of pushing a new one. The recursion runs in constant stack space — it has become a loop.

To get there we carry the running answer forward in an extra parameter, the accumulator, instead of leaving work pending on the way back up:

import scala.annotation.tailrec

def sum(xs: List[Int]): Int = {
  @tailrec
  def loop(rest: List[Int], acc: Int): Int = rest match {
    case Nil       => acc                 // base case: answer is fully built
    case h :: tail => loop(tail, acc + h) // recursive call is the LAST thing — tail position
  }
  loop(xs, 0)                             // start with accumulator = identity for +
}

The @tailrec annotation is the key discipline. It does not make the function tail-recursive; it asks the compiler to verify that it is, and to compile it into a loop. If the call is not actually in tail position, compilation fails with an error — so you can never accidentally ship the stack-overflowing version believing it was optimized. Always annotate the helper you intend to be stack-safe.

4 · Pivot: immutable does not mean deep-copy

Now the worry from Lesson 03. We said "to update, build a new value." Naively that sounds like every change copies the whole structure — change one element of a million-element list and pay a million-element copy. If that were true, immutability would be unaffordable. It is not true. The collections FP uses are persistent data structures: an "update" produces a new version while the old version remains fully valid, and the new version shares all the parts that did not change with the old one. You copy the small slice that differs and reuse the rest by reference.

5 · Cons-list sharing

The cons-list shows persistence in its simplest form. A node is a head cell plus a reference to its tail. Prepending builds one new node pointing at the existing list — the old list is neither copied nor touched:

val a = 2 :: 3 :: Nil   // a:  2 -> 3 -> Nil
val b = 1 :: a          // b prepends 1; b:  1 -> (all of a, reused)
// a is unchanged and still valid. b reuses every node of a.

Prepend is therefore O(1): allocate one node, point it at the old head. Both a and b are real, independent lists that happen to share memory — and that is invisible and harmless, because neither can be mutated. Contrast the two directions: prepending shares the entire existing list; "updating an element in the middle" must rebuild only the path from the front down to that element (the part before it), and shares the unchanged suffix after it. Either way you copy a path, not the whole.

6 · Trees and the wide-trie sketch behind Vector

A list shares well at the front but is O(n) to reach the middle. Scala's Vector and immutable Map get fast arbitrary updates with the same trick applied to a tree. Picture a wide trie: a balanced tree where each internal node has up to ~32 children. A million elements fit in a tree only about four levels deep, because 32 levels multiply fast (32 ⁴ ≈ 1,000,000). To update one element, you copy the path from the root down to the changed leaf — one new node per level — and point every other child reference at the existing, shared subtrees.

7 · Why sharing is safe — and only because of Lesson 03

Here is the load-bearing point. b reuses a's nodes; the updated Vector reuses the old one's subtrees. Sharing memory between two "different" values would be a catastrophe in a mutable world — change the shared part through one alias and the other value silently mutates underneath you (exactly the aliasing bug of Lesson 03). It is safe here only because the shared parts are immutable: no one holds a way to mutate a shared subtree, so two values can point at the same memory forever without ever interfering. Immutability is not the tax that makes persistence necessary; it is the permission that makes sharing — and therefore cheap persistence — possible at all.

loop(1::2::3::4::Nil, 0)   // acc starts at identity 0
loop(  2::3::4::Nil, 1)    // acc = 0 + 1
loop(     3::4::Nil, 3)    // acc = 1 + 2
loop(        4::Nil, 6)    // acc = 3 + 3
loop(           Nil, 10)   // acc = 6 + 4
=> 10                       // base case returns the finished accumulator

Common mistakes / failure modes

Checkpoint exercise

Where this points next

Recursion gave us iteration without mutation; persistence made immutable updates cheap; immutability made sharing safe. Lesson 13 (laziness, streams, and concurrency) spends all three at once. Recursion plus immutable data lets us describe a computation — even a possibly-infinite one, like "all the natural numbers" — as a value, then run only as much of it as we ask for, on demand. The same property that made sharing safe in §7 (nothing mutates) is what makes that description safe to evaluate later, and what makes running pure computations on many threads free of data races. Description-now / execution-later is the bridge from this lesson's structures to the next lesson's LazyList and Future.

Interview prompts

• Why does FP use recursion instead of while loops? (§1 — a loop advances a mutable counter (var i), which FP avoids; recursion calls itself on a strictly smaller piece, expressing iteration with no mutable state.)
• What is structural recursion, and how does it relate to fold? (§1 — one branch per data shape: base case for Nil, recursive case for head :: tail that recurses on the tail; fold is exactly this pattern captured as a HOF taking the base value and combine function, from Lesson 09.)
• Why can naive recursion throw a StackOverflowError, and what is tail recursion? (§2–3 — naive recursion leaves work pending after the call, parking one frame per element; a call is tail-recursive when it is the last thing the function does, letting the runtime reuse the frame and run in O(1) stack.)
• What does the @tailrec annotation actually do? (§3 — it does not make a function tail-recursive; it makes the compiler verify the call is in tail position (failing to compile otherwise) and compile it into a loop, so you cannot accidentally ship the overflowing version.)
• "Doesn't immutability mean copying the whole structure on every update?" (§4–6 — no; persistent structures share unchanged parts. Cons prepend is O(1) sharing the whole tail; Vector is a ~32-way trie where an update copies only the ~4-node root-to-leaf path of a million-entry structure — O(log₃₂ n), not O(n).)
• Roughly how many nodes does updating one element of a 1,000,000-entry Vector copy, and why? (§6 — about 4 small nodes: the tree is ~4 levels deep (32 ⁴≈1M), so only the root-to-changed-leaf path is rebuilt; every other subtree is shared by reference.)
• Why is structural sharing safe? (§7 — only because the shared parts are immutable: no alias can mutate a shared subtree, so two versions can point at the same memory without interfering — the very aliasing bug Lesson 03 ruled out.)
• Which of foldLeft/foldRight is stack-safe on a long List? (Common mistakes — foldLeft; it is tail-recursive with an accumulator, whereas foldRight on a plain list recurses to the end first and can overflow.)