Recursion and Immutable Data: Writing Loops Without `for` (Part 3 of the Functional Programming Series)

Part 3 of the Functional Programming in Practice series. Parts 1 and 2 covered pure pipes and how to compose them. Now we deal with the thing that makes most people think functional programming is insane: there are no loops.

Hey there, Coding Chefs! 👨‍💻

The first time someone told me functional programming has no for loops and no while loops, I assumed they were exaggerating for effect. They were not. In strict functional style, those keywords simply do not exist. No for, no while, no i++.

The reason you reach for a loop is almost always the same: you set up a variable, then you mutate it over and over until it holds the answer. Sum a list? Start total at 0 and keep adding to it. That mutation is exactly what the first part told us to give up. We believe mutation is a primary source of human error and bugs, so we are not going to do it. Which raises the obvious panic: if I cannot mutate a counter and I cannot write a loop, how do I process a list of a thousand things?

The answer is recursion, and once it clicks it is genuinely beautiful. By the end of this article you will model any loop you have ever written as a recursive function, you will understand why linked lists feel so natural in functional code, and we will have the honest talk about when a plain for loop is still the right tool. Let's get cracking.

The Problem: Sum a List Without Mutating

Let's take the most ordinary task imaginable. Sum an array of numbers. Here is how every one of us learned to do it:

const sumAll = (nums: number[]): number => {
  let result = 0;             // set up a variable
  for (const n of nums) {
    result = result + n;      // mutate it over and over
  }
  return result;              // until it holds the answer
};

We declared result, initialized it to 0, then mutated it on every pass through the loop until it reached the final state we wanted. Functional programming forbids that mutation. So we need another way to look at the problem.

Let's stare at the array and ask a different question. Instead of "how do I walk through this," ask "can I describe the answer in terms of a smaller version of the same problem?"

Split the array into two parts: the first element (the head), and everything else (the tail).

[1, 2, 3, 4]
 head = 1
 tail = [2, 3, 4]

Now the aha moment. If I already knew the sum of the tail [2, 3, 4], then the sum of the whole array is just head + sum of the tail. The sum of [1, 2, 3, 4] is 1 + sum([2, 3, 4]). I defined the answer using a smaller version of the same question. That is what recursive means: the function is defined in terms of itself.

If that bends your brain a little, pause and reread it, because that one sentence is the entire concept. Once you see that the sum of a list is the head plus the sum of the rest, you understand recursion.

The Base Case: Where Recursion Stops

There is one piece left. "The sum is the head plus the sum of the tail" keeps shrinking the list. Eventually the tail is empty. What is the sum of an empty array?

Take a second to answer it yourself. The sum of nothing is 0. That is the base case: the input small enough that we already know the answer directly, without recursing further. The base case is where all the deferred values finally materialize and the recursion bottoms out.

Now we have everything. A recursive function is just two things: the base case (the answer when the input is smallest) and the recursive case (the answer in terms of a smaller input).

const sumAll = (nums: number[]): number => {
  if (nums.length === 0) return 0;          // base case
  const [head, ...tail] = nums;             // split head / tail
  return head + sumAll(tail);               // recursive case
};

sumAll([1, 2, 3, 4]); // 10

No let. No mutation. No loop. We never changed a variable. We described the answer and let the function unfold itself. Trace it by hand once and watch it bottom out:

sumAll([1,2,3,4])
= 1 + sumAll([2,3,4])
= 1 + (2 + sumAll([3,4]))
= 1 + (2 + (3 + sumAll([4])))
= 1 + (2 + (3 + (4 + sumAll([]))))
= 1 + (2 + (3 + (4 + 0)))      // base case hit
= 10

And because sumAll is a pure function (one input, one output, no side effects, as purity demanded), it is still just a pipe. An array goes in the left, a number comes out the right. That means it composes like any other pipe, so you can drop it straight into the pipe and compose machinery we built earlier.

Arrays Versus Linked Lists

The recursion above used a JavaScript array, which is comfortable. But arrays have a property worth understanding, because it explains why functional languages reach for a different structure so often.

An array is a collection of items stored right next to each other in memory, each at a fixed-size slot. That layout is what makes random access fast. If you want the item at index 3, the runtime knows the start address and the size of each slot, so it jumps straight there with a little arithmetic. Index access is effectively instant.

The cost shows up when you insert into the middle. To insert an item at the front or middle of an array, you have to shift everything after it over by one slot, which means touching every later element. For a single insert near the front, you pay for the whole tail of the array.

The other classic structure for a sequence is the linked list. A linked list is also an ordered collection, but the items do not sit next to each other in memory. Each item is a node that holds a value plus a pointer to the next node. To insert a new node, you just repoint two pointers, no shifting of everything else. The trade is that you lose instant index access, because to reach item number four you have to walk node by node from the front.

Here is why linked lists feel so at home in functional programming. Look at how a linked list is defined: it has a head (the first node) and a tail (the rest of the list). But the tail is itself a linked list, with its own head and its own tail. The definition refers to itself. A linked list is recursive by its very nature, which is exactly the head/tail shape our sumAll was already using. The structure and the way we process it are the same idea.

In TypeScript we can model a linked list as a sum type (we will go deep on those in a later part). A list is either an empty end marker, or a node holding a value and pointing at the rest:

type List<A> =
  | { tag: "nil" }                        // the empty list, the end
  | { tag: "cons"; head: A; tail: List<A> }; // a node: value + rest

const nil: List<never> = { tag: "nil" };
const cons = <A>(head: A, tail: List<A>): List<A> => ({ tag: "cons", head, tail });

const myList = cons(1, cons(2, cons(3, nil))); // 1 -> 2 -> 3 -> end

Summing it is the same head/tail recursion as before, just reading the shape of the structure directly:

const sumList = (list: List<number>): number =>
  list.tag === "nil" ? 0 : list.head + sumList(list.tail);

The base case is nil. The recursive case is head plus the sum of the tail. The data structure and the algorithm mirror each other perfectly. That is the elegance functional programmers keep talking about.

The Honest Performance Talk

Now, you are probably thinking the practical thought: isn't recursion slower and heavier on memory than a good old for loop? Sometimes, yes. I am not going to pretend otherwise.

Every recursive call adds a frame to the call stack. Our sumAll traced out as a tower of pending additions, all waiting on the stack until the base case came back. For a list of a few thousand items that is fine. For a list of a few hundred thousand, you can blow the stack and crash with a stack-overflow error. A plain for loop has no such tower, it just updates one slot.

There are two honest responses to this.

First, the theory response: functional programming is mostly about modeling a problem cleanly and reasoning about it soundly, not about squeezing the transistors. The recursive definition is the clearest possible statement of what summing a list means. That clarity has real value even before performance enters the chat.

Second, the practical response: there are techniques to make recursion efficient when it matters. Tail recursion rewrites the function so the recursive call is the very last thing it does, carrying the running total along as an argument instead of leaving a tower of pending work:

const sumAll = (nums: number[], acc = 0): number =>
  nums.length === 0 ? acc : sumAll(nums.slice(1), acc + nums[0]);

In languages that guarantee tail-call optimization, this runs in constant stack space, like a loop. JavaScript engines, frustratingly, do not reliably optimize tail calls today, so for genuinely huge inputs in JS you either reach for a technique called trampolining (which turns the recursion into a loop under the hood) or you accept a real loop on that one hot path. And honestly, reduce is the tool most of us reach for, which is itself just folding a list down to a value, a pattern we will name properly when we get to Foldable.

This is the non-dogmatic stance I want you to hold: prefer the clear recursive or declarative model, reach for the imperative loop without guilt on the rare hot path where you have measured a real problem. Choosing a for loop because you profiled and it matters is good engineering. Choosing it out of habit is the thing we are training away.

Immutability and the Fear of Copying

Recursion handled the "no loops" half of this article. The other half is the data itself. The first part said we never mutate, we always derive a new value. Let's make that concrete and then face the obvious objection.

// the reflex
const arr = [1, 2, 3];
arr.push(4); // mutated the original, anyone else holding arr is affected

// the functional move
const arr = [1, 2, 3];
const next = [...arr, 4]; // new array, original untouched

Same with objects:

const updated = { ...user, name: "Adébáyọ̀" }; // new object, old one safe

The objection writes itself: copying on every change sounds wasteful. If I have a list of ten thousand items and I add one, am I really copying ten thousand items every time?

In practice, usually no, and the reason is a clever idea called structural sharing. Persistent data structures, the kind that power libraries like Immer and Immutable.js, do not deep-copy the whole thing on update. They build a new version that quietly shares most of its internals with the old version, only creating new nodes along the path that actually changed. You get a brand new value that behaves as if it were a full copy, while most of the memory is reused under the hood. "Copy on update" turns out to be far cheaper than the words suggest. The full mechanics deserve their own treatment, but the headline is enough for now: immutability does not mean ruinous copying.

And remember what immutability buys you, the same payoff we named at the start. Nobody can change your data out from under you. No spooky action where a value mutates because some far-off function held a reference. You can hand the same list to ten functions and know all ten see the same thing. That safety is worth a great deal more than the occasional copy.

The Honest Conclusion

Functional programming drops for and while not to be difficult, but because those loops are built on the mutation we already agreed to give up. Recursion replaces them by asking a better question: can I describe this answer in terms of a smaller version of the same problem, plus a base case where I already know the answer? Once you see the head-plus-sum-of-the-tail shape, you can rewrite any loop, and linked lists fall out as the structure that mirrors that shape exactly.

The performance worries are real but manageable. Tail recursion, trampolining, reduce, and the honest fallback to a real loop on a measured hot path are all in your toolbox. Default to the clear model, drop to the loop with intent.

And immutability, the partner to all of this, is cheaper than it sounds thanks to structural sharing, while paying you back in data you can actually trust.

Stop asking how to walk through the data. Start asking what the answer is in terms of a smaller piece of it. That single shift is recursion, and it is how functional code loops.

Next up: We go after the most common crash in any codebase, the one that reads Cannot read property 'x' of undefined. Next we kill null for good with Option, and you will finally see why "this type has exactly one more value than that one" is the precise tool that ends a whole category of bugs.