Foundations

Recursion

A function that calls itself on a smaller subproblem. The call stack manages the rest.

The shift

Recursion clicks when you stop thinking about how the call stack works and start thinking about what the function promises.

Define what the function returns for a single element. Trust that definition when you call it on sub-problems. That's it.

// Promise: returns the sum of all values in a tree rooted at `node`
function sum(node) {
  if (!node) return 0;
  return node.value + sum(node.left) + sum(node.right);
  //                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  //                   Trust the promise for subtrees.
}

The call stack handles the bookkeeping. Your job is just to define the contract.

Why it's everywhere in software

Recursive algorithms naturally fit recursive data structures — structures where instances contain other instances of the same type. These show up constantly:

Trees (left/right are also trees)
Nested lists (items can contain lists)
File systems (folders contain folders)
JSON objects (values can be objects)
Component trees (components render components)

If the data is recursive, the algorithm almost always wants to be recursive too. Fighting that with iteration usually means manually maintaining a stack — which is just implementing the call stack yourself.

When to stop using it

Recursion hands its state to the call stack. That's elegant but inflexible:

Stack overflow — deep trees crash (V8 limit: ~10,000 frames).
Can't pause — once in the call stack, you can't yield control back to the caller mid-traversal.
Can't prioritize — all recursive calls are equal; you can't say "process this subtree first."

When you hit any of those constraints, you convert the recursion to an explicit stack (a while loop + an array). You're writing the same algorithm; you've just moved the stack from the language runtime into your own data structure. React Fiber's entire architecture is this trade made for a real production reason.

Connections

How this links to the rest

Stack — Every recursive call pushes a frame onto the call stack — return pops it. Recursion is implicit stack usage. Converting recursion to iteration means making that stack explicit, which is exactly what iterative DFS does.
Binary Tree — A binary tree is a recursive data structure: a node whose children are also binary trees. The recursion terminates at null. The shape of the data IS the shape of the recursion — they're the same thing viewed differently.
Linked List — A linked list is a recursive structure: a head node followed by another linked list. Processing it recursively (walk the tail, prepend result) is the same pattern as tree recursion — just one child instead of two.
Tree Traversal — Tree traversal is the canonical recursive algorithm: process the current node, recurse on each child. The call stack manages the traversal state so you don't have to.
Depth-First Search — Recursive DFS is: mark the current node visited, recurse on each unvisited neighbor. The call stack IS the DFS stack. Iterative DFS makes this explicit by maintaining a manual stack.
Divide and Conquer — Divide and conquer is recursion with a combine step. Split the problem into subproblems of the same type, recurse, combine. The recursive structure is what makes the split/combine pattern work.
Dynamic Programming — DP is recursion with caching. The recursive structure identifies overlapping subproblems; the cache prevents recomputing them. Remove the cache: exponential time. Add it: polynomial time.
Backtracking — Backtracking is recursive DFS on the space of partial solutions. The recursive call explores one choice; the return undoes it. The recursive structure is what makes 'undo' natural.
React Fiber — React 15 reconciled the component tree recursively. Recursion can't yield control mid-traversal. React 16 solved this by converting the implicit call stack into an explicit Fiber linked list — same DFS, different bookkeeping.
DOM Walking — Recursive DOM walking works because DOM nodes are a recursive data structure — an Element contains Elements. The recursion terminates at leaf nodes (no children).