Basic recursion

Trees, backtracking, DP and divide-and-conquer are all recursion wearing a costume.

Every recursive function is two things

A base case (the answer you can state directly, no further calls needed) and a recursive case (the problem restated in terms of a smaller version of itself). Skip the base case and you get infinite recursion; get the smaller-version part wrong and it either never terminates or terminates with the wrong answer.

function factorial(n) {
  if (n <= 1) return 1;           // base case — the floor
  return n * factorial(n - 1);    // recursive case — smaller problem
}

The call stack is a real stack — draw it

Nothing multiplies until the base case is hit — then the answers flow back up.

⚠ Recursion isn't free space Every call sits on the stack until it returns — n nested calls is O(n) space, not O(1), even though you never wrote new Array() anywhere. Deep enough recursion (tens of thousands of levels in JS) throws a real RangeError: Maximum call stack size exceeded. This is a legitimate interview follow-up: "can you do this iteratively instead?"

Recursion on arrays — shrink by one end

function sum(arr, i = 0) {
  if (i === arr.length) return 0;      // base case: ran off the end
  return arr[i] + sum(arr, i + 1);      // smaller problem: one fewer element left
}

function reverseString(s) {
  if (s.length <= 1) return s;
  return reverseString(s.slice(1)) + s[0]; // reverse the rest, then tack on the first char
}

Recursion on trees — the shape you'll use constantly later

function treeHeight(node) {
  if (node === null) return 0;               // base case: empty subtree
  return 1 + Math.max(
    treeHeight(node.left),
    treeHeight(node.right)
  );                                          // combine two smaller answers
}

Notice this recursion branches into two calls, not one — that's the exact shape the Trees chapter builds on, and it's why tree recursion complexity is usually expressed in terms of the number of nodes visited, not a simple "n halves each time" story.

Multiple recursive calls — the branching factor matters

Naive Fibonacci recomputes the same subproblems over and over — fib(5) calls fib(3) twice, fib(2) three times, and so on. That's O(2ⁿ) work for what's conceptually an O(n) amount of distinct information — memoization (its own chapter, under Dynamic Programming) is exactly the fix: cache each distinct call so it only ever computes once.

// O(2ⁿ) — recomputes the same subproblems repeatedly
function fibSlow(n) {
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

This is what "each call branches into two more calls" actually looks like — and why it explodes.

Say it like this → "The base case is the smallest input I can answer directly without recursing, and the recursive case restates the problem on a strictly smaller input — as long as it's strictly smaller every time, the recursion is guaranteed to terminate."

Converting recursion to iteration (when asked)

Any recursion can be rewritten iteratively using an explicit stack that mimics what the call stack was doing — this is worth being able to do live, since "avoid the call stack" is a common follow-up.

// factorial, iteratively — no call stack growth
function factorialIter(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}

Recognizing it in an unseen problem

The structure itself is recursive — trees, nested lists, nested objects
The problem can be restated as "solve it for a smaller version, then combine"
Words like "all combinations," "all paths," "every way to" — usually backtracking, built on this same base/recursive-case shape
If the same sub-inputs repeat across branches, that's your cue to add memoization rather than leaving it as plain recursion

Practice this layer

Opens in the editor — write it, run it, and check it against real tests.

Fibonacci with Memoisation5 tests · beginner Pow(x, n) — Fast Exponentiation5 tests · intermediate Generate All Subsets5 tests · beginner Flatten a Deeply Nested Array5 tests · beginner

function sum(arr, i = 0) { if (i === arr.length) return 0; // base case: ran off the end return arr[i] + sum(arr, i + 1); // smaller problem: one fewer element left } function reverseString(s) { if (s.length <= 1) return s; return reverseString(s.slice(1)) + s[0]; // reverse the rest, then tack on the first char }

function treeHeight(node) { if (node === null) return 0; // base case: empty subtree return 1 + Math.max( treeHeight(node.left), treeHeight(node.right) ); // combine two smaller answers }