Basic recursion

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
}

Dry run: factorial(4)

Nothing multiplies until factorial(1) hits the base case — every call above it is suspended mid-expression, waiting on its own recursive call to resolve. That's exactly the four simultaneously-alive stack frames the space warning below is about: the actual arithmetic only happens on the way back up, never on the way down.

The call stack is a real stack — draw it

The leap of faith: write one step, trust the call

The dry run above shows what recursion does. It is a poor way to write it: if you try to hold five suspended calls in your head while you decide the next line, you will lose the thread by the fourth. Write it the way a proof by induction is written. Assume the function already returns the right answer for every smaller input, and write only the step that turns that answer into yours. Three questions, in this order, and the function mostly falls out:

• What is the smallest input I can answer without a recursive call? That is the base case. Check that it covers every smallest input, not just the one you were thinking of.
• If someone handed me the correct answer for a smaller input, what would I do with it? That is the recursive case. It is one step, not a plan for the whole recursion.
• Is the input I hand down strictly smaller, so the base case is eventually reached? That is the progress check, and it is where most infinite recursions are born.

function sumDigits(n) {
  if (n < 10) return n;                            // base: one digit, the answer is the number itself
  return (n % 10) + sumDigits(Math.floor(n / 10));  // last digit + (trust: the rest is already right)
}

function isPalindrome(s, lo = 0, hi = s.length - 1) {
  if (lo >= hi) return true;                 // base: zero or one character left
  if (s[lo] !== s[hi]) return false;          // the outer pair can settle it alone
  return isPalindrome(s, lo + 1, hi - 1);     // otherwise trust the inside
}

Notice what the bodies do not contain: no loop over the digits, no bookkeeping about how many calls are pending. sumDigits(4072) is 2 + sumDigits(407), and you are allowed to believe sumDigits(407) without opening it up. That permission is the leap of faith, and it is justified: the base case is correct, and if every call on a smaller input is correct then so is the step built on it, so by induction every size is correct.

Dry run: isPalindrome("abca") and isPalindrome("abba")

The last row is the reason the base case says lo >= hi and not lo === hi. A string of even length shrinks from both ends and the two indices cross without ever being equal. With === the call on "abba" carries on to (3, 0), then to indices off both ends of the string where undefined === undefined keeps the comparison happy, and finally throws a RangeError. When you write a base case, list every input size that can arrive there, not just the one you drew.

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
}

Slicing hides a cost: count what each call copies

reverseString above is correct, but it is not the O(n) that its single recursive call suggests. Each call runs s.slice(1), which builds a new string of every character except the first, and then + s[0] builds another. The calls make n − 1, n − 2, … 1 characters' worth of copies, and that adds up to n(n − 1) / 2. Treat that as the cost model: one call per character, each call doing O(n) copying work, so O(n²) time overall. (An engine is free to share storage between a string and its slice, but you cannot rely on it and an interviewer will not grant it, so say O(n²).) The same trap appears in arrays whenever the recursion is written as f(arr.slice(1)) or f([...rest]).

Those counts were measured by wrapping String.prototype.slice in node and adding up the lengths it returned (499,500 for a 1,000-character string), so they match the formula exactly. The fix is to stop making smaller copies and instead pass indices that describe the smaller problem. The recursion shape is identical and each call does O(1) work:

function reverseInPlace(chars, lo = 0, hi = chars.length - 1) {
  if (lo >= hi) return chars;                         // base: zero or one element left
  [chars[lo], chars[hi]] = [chars[hi], chars[lo]];     // swap the outer pair
  return reverseInPlace(chars, lo + 1, hi - 1);        // trust the inside
}
// reverseInPlace(["a","b","c","d"]) → ["d","c","b","a"]

This does about n / 2 calls, each O(1), so O(n) time, and the call stack gets about n / 2 deep, so O(n) space for the stack. It reverses the array it is given; strings are immutable in JavaScript, so you reverse [...s] and join the result at the end. The general rule worth saying out loud: pass the boundaries of the subproblem, not a copy of it. Binary search, merge sort on index ranges and every backtracking routine later in the course follow it.

Return it up, or carry it down

A recursive call can communicate in two directions. So far the answers have flowed up: each call returns a value, and the caller combines it (sum, treeHeight). The other option is to flow information down: the caller hands the call what has happened so far as an extra parameter, and the call either reports it at the base case or records it somewhere shared. The same sum, both ways:

function sumReturn(arr, i = 0) {              // answer flows UP
  if (i === arr.length) return 0;
  return arr[i] + sumReturn(arr, i + 1);      // the addition waits until the call returns
}

function sumCarry(arr, i = 0, total = 0) {    // answer flows DOWN, in the parameter
  if (i === arr.length) return total;         // the finished total is simply passed back up
  return sumCarry(arr, i + 1, total + arr[i]);
}

sumCarry has nothing left to do after the recursive call, which is called a tail call. In some languages that lets the compiler reuse the frame. Do not count on it in JavaScript: calling sumCarry on an array of 100,000 elements throws a RangeError in node, exactly like sumReturn would. Carrying the total down changes the shape of the code, not the stack depth. If depth is the problem, use a loop or the explicit stack from the conversion section below.

Carrying state down earns its keep when the answer depends on where you are rather than on the children: the depth of a node, the sum of the path so far, the list of choices made so far. Those need a parameter, and the extra parameters are an implementation detail the caller should not see. The standard shape is a clean public function wrapping an inner helper that carries the state:

function deepestLeafDepth(root) {
  let best = 0;                                // shared by every call of walk
  function walk(node, depth) {                 // depth is carried DOWN
    if (node === null) return;
    best = Math.max(best, depth);
    walk(node.left, depth + 1);
    walk(node.right, depth + 1);
  }
  walk(root, 1);
  return best;
}

This returns the same number as treeHeight from the tree section below, computed in the other direction. Return up when the answer is built from the answers to the smaller pieces (height, size, count). Carry down when it depends on the route taken to reach a node (depth, running total, the path itself). Plenty of tree problems do both at once, such as the maximum path sum, which the tree chapters cover.

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.

Nested data: when the input is the recursion

Sometimes you never choose to recurse, because the data is already recursive: an array that can contain arrays, a JSON object whose values can be objects. The tree pattern applies unchanged, with one twist worth stating plainly. The base case is not "empty", it is "this is not a container": a number, a string, null. Everything else is a node with children to visit.

function flatten(value, out = []) {
  if (!Array.isArray(value)) {               // base: a leaf, not a container
    out.push(value);
    return out;
  }
  for (const item of value) flatten(item, out);  // out is carried down and filled in place
  return out;
}

function nestingDepth(value) {
  if (!Array.isArray(value)) return 0;       // a leaf adds no nesting
  let deepest = 0;
  for (const item of value) deepest = Math.max(deepest, nestingDepth(item));
  return 1 + deepest;                        // this array itself is one level
}

Dry run: nestingDepth([1, [2, [3]], 4])

flatten was checked against the built-in arr.flat(Infinity) on random nested arrays. Time is O(total number of values and arrays), because every element is visited once, and the stack depth equals the nesting depth. A tempting shorter version, out.push(...flatten(item)), spreads each inner result into function arguments, and in node spreading an array of 150,000 elements into a call already throws a RangeError; carrying out down avoids both that and the repeated copying.

The same shape handles objects, with three details that cost people offers:

function sumNumbers(value, seen = new Set()) {
  if (typeof value === "number") return value;
  if (value === null || typeof value !== "object") return 0;  // null is typeof "object"!
  if (seen.has(value)) return 0;                              // already visited: breaks cycles
  seen.add(value);
  let total = 0;
  for (const child of Object.values(value)) total += sumNumbers(child, seen);
  return total;
}

• typeof null === "object". Without the explicit null check, Object.values(null) throws a TypeError the first time a null value appears.
• Cycles. If a.self = a, plain recursion never reaches a leaf and ends in a RangeError. The seen set records the containers already entered. (JSON has no cycles, which is why JSON.stringify throws on one.)
• Shared references. The same seen set also skips an object that is merely reachable twice. For [shared, shared] where shared = { x: 1 }, this version returns 1 and a version without seen returns 2. Decide which answer the question wants, and say so.

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);
}

Memoized Fibonacci: each distinct call runs once

The tree above is wasteful because fibSlow(2) means the same thing wherever it appears. A call is determined by its argument, so the first time you compute it, write the answer down; every later request is a lookup. That is all memoization is: a cache keyed by the arguments.

function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);                       // seen this argument: reuse the answer
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);                                        // store before returning
  return result;
}

Dry run: fibMemo(5), in the order things happen

That is nine calls in total for fibMemo(5), against fifteen for fibSlow(5). The gap widens fast: counting every call, fibSlow(30) makes 2,692,537 calls and fibMemo(30) makes 59. In general memoized Fibonacci makes 2n − 1 calls: each of the n − 1 arguments from 2 to n is computed once and makes two calls, plus the first call.

The cost rule you will use from here on: time = (number of distinct states) × (work per state). Here there are n states and each does O(1) work besides its calls, so O(n). Space is the n memo entries plus the call stack, also O(n). When the loop version of the same recurrence is allowed, it drops the stack entirely:

function fibLoop(n) {
  let prev = 0, curr = 1;                          // fib(0), fib(1)
  for (let i = 0; i < n; i++) [prev, curr] = [curr, prev + curr];
  return prev;
}

Halving the problem: fast exponentiation

Computing xⁿ as n − 1 multiplications is O(n), and for a large n that is too slow. Notice what squaring does: x¹⁰ = (x⁵)², and x⁵ = x · (x²)². In general, if you already have the answer for ⌊n / 2⌋, one squaring gets you the answer for n, with one extra factor of x when n is odd. The problem shrinks by half per call, so there are about log₂ n calls instead of n.

function power(x, n) {
  if (n === 0) return 1;                        // base: x⁰ = 1, even for x = 0 by convention
  if (n < 0) return 1 / power(x, -n);          // negative exponent: reciprocal of the positive one
  const half = power(x, Math.floor(n / 2));     // ONE call, result reused
  return n % 2 === 0 ? half * half : half * half * x;
}

Dry run: power(2, 10)

Five calls for n = 10. The count is ⌊log₂ n⌋ + 2, which counting calls in node confirms for n = 10, 1,024 and 1,000,000 (5, 12 and 21 calls). Time is O(log n), and the call stack is the same depth, so O(log n) space. A million-fold larger exponent adds only about twenty calls.

Two practical notes. Floating point: the squaring order multiplies in a different sequence than the loop, so the last digits differ. power(1.0001, 10000) gave 2.718145926824389 while Math.pow(1.0001, 10000) gave 2.7181459268249255. Both are right to about twelve digits, so compare floating results with a tolerance. Modular exponentiation (find xⁿ mod m, ubiquitous in number theory and hashing questions) uses the same halving, but the products grow past 2⁵³ in plain numbers: for m = 1,000,000,007 the square of m − 1 is about 10¹⁸, which a number cannot hold exactly. Use BigInt, and the loop form of the halving, which walks the bits of the exponent:

function powMod(base, exp, mod) {                 // all three are BigInt
  let result = 1n;
  base %= mod;
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % mod;   // this bit of the exponent is set
    base = (base * base) % mod;                    // base, base², base⁴, base⁸, ...
    exp >>= 1n;
  }
  return result;
}
// powMod(2n, 1000000n, 1000000007n) → 235042059n

Choose or don't choose: generating subsets

"All subsets" looks like it needs clever bookkeeping until you ask what a subset is: for each element, you either took it or you did not. That is a recursion with two calls per element, one for each choice, and a base case when every element has been decided. The "answer so far" is the array of chosen elements, carried down.

function subsets(nums) {
  const all = [];
  const current = [];
  function decide(i) {
    if (i === nums.length) {
      all.push([...current]);        // COPY: current keeps changing after this
      return;
    }
    decide(i + 1);                   // choice 1: leave nums[i] out
    current.push(nums[i]);           // choice 2: take it ...
    decide(i + 1);
    current.pop();                   // ... then undo, so the caller sees current unchanged
  }
  decide(0);
  return all;
}
// subsets([1, 2, 3]) → [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Dry run: the eight leaves of subsets([1, 2, 3])

The recursion tree has 2ⁿ leaves, one per subset, and 2ⁿ⁺¹ − 1 calls in all (15 for n = 3). Each leaf copies up to n elements, so time is O(n · 2ⁿ); the stack is n + 1 deep and current holds at most n elements, so the working space is O(n) not counting the output. This is the template that the backtracking chapter develops into permutations, combinations and pruning.

The same tree answers a counting question without building any list, which is the "return up" direction again. How many subsets sum to target? Subtract the chosen element from the target and ask whether the remainder reaches exactly 0 at the end:

function countSubsets(nums, target, i = 0) {
  if (i === nums.length) return target === 0 ? 1 : 0;   // all decided: did we land exactly?
  return countSubsets(nums, target, i + 1)                // leave nums[i] out
       + countSubsets(nums, target - nums[i], i + 1);     // take it
}
// countSubsets([1, 2, 3], 3) → 2   ({3} and {1, 2})

It runs in O(2ⁿ) time and, because it keeps no list, O(n) stack space. Each call is determined by the pair (i, target), so when many different paths reach the same pair, this is the repeated-subproblem shape from the Fibonacci section and a memo (or a table, in the dynamic programming chapters) collapses the exponential into a polynomial. Zeros and negative numbers are handled correctly because the empty remainder is only tested at the end; nums = [0, 0] with target 0 counts all four subsets.

Two classics: gcd and the Tower of Hanoi

Euclid's gcd is the shortest serious recursion there is, and its correctness is the leap-of-faith argument in miniature. Any number that divides both a and b also divides a − q·b for any whole q, in particular the remainder a % b, and the reverse is true too, so gcd(a, b) = gcd(b, a % b). The second argument strictly shrinks (a % b < b), so it reaches 0, where the answer is the first argument.

function gcd(a, b) {
  if (b === 0) return a;           // nothing left to divide by: a is the answer
  return gcd(b, a % b);
}

How many calls? If b ≤ a / 2 then a % b < b ≤ a / 2, and if b > a / 2 then a % b = a − b < a / 2. Either way the remainder is less than half of a, so every two calls the larger argument at least halves, which gives O(log(min(a, b))) calls. The slowest inputs are consecutive Fibonacci numbers: gcd(1346269, 832040), which are fib(31) and fib(30), takes 30 calls. Edge cases: gcd(a, 0) is a, gcd(0, 0) returns 0 (undefined mathematically; decide what you want), and a negative input can leak out as a negative answer because % keeps the sign of its left operand: gcd(4, -6) returns -2. Apply Math.abs to both arguments at the entry if negatives are possible. For the least common multiple use a / gcd(a, b) * b, dividing first so the intermediate product stays small.

The Tower of Hanoi is the classic case where thinking recursively is much easier than thinking about moves. Move n disks from peg A to peg C using B as a spare, one disk at a time, never putting a larger disk on a smaller one. Leap of faith: suppose you can already move n − 1 disks between any two pegs. Then move the top n − 1 to the spare peg, move the biggest disk once, and move the n − 1 on top of it. Nothing else is needed.

function hanoi(n, from, to, via, moves = []) {
  if (n === 0) return moves;                    // no disks: nothing to move
  hanoi(n - 1, from, via, to, moves);           // trust: top n-1 get out of the way, onto via
  moves.push([from, to]);                       // the largest disk moves exactly once
  hanoi(n - 1, via, to, from, moves);           // trust: the n-1 go back on top, onto to
  return moves;
}
// hanoi(3, "A", "C", "B") → A→C, A→B, C→B, A→C, B→A, B→C, A→C

For n = 3 that is seven moves. A simulation that replays every move confirmed that each is legal and that the disks end up stacked on C for every n up to 10. The move count satisfies M(n) = 2 · M(n − 1) + 1 with M(0) = 0, so M(n) = 2ⁿ − 1. No shorter solution exists: to move the largest disk, the other n − 1 must be sitting on the third peg, which takes at least M(n − 1) moves, and after the largest disk moves, they must travel again, which takes at least M(n − 1) more. So the minimum is at least 2M(n − 1) + 1, the same recurrence. The recursion is only n + 1 deep but the work is exponential: 20 disks need 1,048,575 moves, and 64 disks need about 1.8 × 10¹⁹. If you only need the count, return 2 ** n - 1 instead of storing the moves. The rotating roles of from, to and via in the two recursive calls are the usual place to slip.

Reading the cost off the recursion tree

Every function in this chapter can be costed the same way. Draw the recursion tree, then:

• Time = (number of calls in the tree) × (work each call does itself, not counting its recursive calls). When the work per call varies, add it up level by level.
• Stack space = (depth of the tree) × (what each frame holds). Add whatever you build on the side, such as a memo or an output list.

The call counts for the Fibonacci, power and subsets rows were measured by counting calls in node, and the Fibonacci one matches the formula 2 · fib(n + 1) − 1 for n = 5, 10, 20 and 30 (15, 177, 21,891 and 2,692,537). Two reading habits pay off. First, count distinct states when a call is determined by its arguments: that is what memoization turns the call count into. Second, check whether "work per call" is really constant. slice and spread look like one operation and are not, which is the entire gap between the two reversals above. The same tree-reading carries over to merge sort in the next chapter, where the work per call is the size of the merge and the levels add up to n log n.

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;
}

How deep is too deep? Measure it, then own the stack

"Maximum call stack size exceeded" is not a number of calls, it is a number of bytes of stack, so a function with more parameters and local variables overflows sooner. You can measure your own engine in two lines:

let depth = 0;
function dive() { depth++; dive(); }
try { dive(); } catch (e) { console.log(depth, e.constructor.name); }

On Node 24 this printed a little over 10,000 for the bare function above, and a little over 4,000 for a function with six parameters and four locals, each followed by RangeError. Browsers and other Node versions differ, so never write code that depends on a specific number. The practical rule: a recursion whose depth is proportional to the input (a linked list or skewed tree of 100,000 nodes, a path in a big grid) is a risk, while one whose depth is logarithmic (power, balanced trees) is not.

When depth is the risk, move the call stack into your own array. The recipe is mechanical. A stack frame is just the arguments plus "where I was in the function", so push the arguments instead of calling, and loop until the stack is empty. If the function does work after a recursive call returns, that pending work becomes a frame of its own, pushed before the calls it waits on, because the last item pushed is the first one run. First the easy case, where the state is carried down, so a frame is just [node, depth]:

function treeHeightIterative(root) {
  if (root === null) return 0;
  let best = 0;
  const stack = [[root, 1]];                   // each frame: a node and its depth
  while (stack.length) {
    const [node, depth] = stack.pop();
    best = Math.max(best, depth);
    if (node.left) stack.push([node.left, depth + 1]);
    if (node.right) stack.push([node.right, depth + 1]);
  }
  return best;
}

It returns the same height as treeHeight on random trees, and on a 200,000-node chain it returns 200,000 where the recursive version throws a RangeError. The stack now lives on the heap and is limited by memory, not by the call-stack size. The harder case is a function with work between its calls, such as hanoi, where the move must happen after the first recursive call and before the second. Give the stack two kinds of frame, "solve this subproblem" and "perform this move", and push them in the reverse of the order they should run:

function hanoiIterative(n, from, to, via) {
  const moves = [];
  const stack = [{ n, from, to, via }];                              // a subproblem to solve
  while (stack.length) {
    const f = stack.pop();
    if (f.move) { moves.push([f.from, f.to]); continue; }           // a pending move: perform it
    if (f.n === 0) continue;
    stack.push({ n: f.n - 1, from: f.via, to: f.to, via: f.from });  // runs LAST (pushed first)
    stack.push({ move: true, from: f.from, to: f.to });              // runs in the middle
    stack.push({ n: f.n - 1, from: f.from, to: f.via, via: f.to });  // runs FIRST (pushed last)
  }
  return moves;
}

For every n from 0 to 12 this produces exactly the same list of moves, in the same order, as the recursive hanoi. The reversal is the part to rehearse: reading the three pushes top to bottom gives the opposite of the execution order, because a stack is last in, first out. Same time, O(n) space. A plain loop is simpler than an explicit stack when the recursion is a single chain, as in factorialIter and fibLoop. Reach for the explicit stack when the recursion branches.

The mistakes that cost points

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
• "For each item, take it or leave it" is a two-call recursion over the items, and the number of calls is the first thing to estimate (2ⁿ here)
• The input is cut in half each call and only one half is used (exponent, search range): expect O(log n) calls, and check you are making one call, not two
• The answer depends on the route taken to reach a node (depth, running total, path): carry that state down as a parameter; if it is built from the children's answers, return it up
• The prompt gives a depth that would overflow the stack, or asks you to "do it without recursion": use a loop for a chain, an explicit stack for a branching recursion