Recursion

A function that solves a problem by calling itself on a smaller version of the same problem.

What is it?

Some problems are naturally defined in terms of smaller versions of themselves — finding the total of a list, exploring every folder inside a folder, calculating a factorial. Recursion is when a function solves such a problem by calling itself with a smaller input, until the input is simple enough to answer directly (the base case).

Every recursive function needs two things: a base case that stops the recursion, and a step that reduces the problem toward that base case.

Explain like I'm 10

Recursion is like a set of Russian nesting dolls. To find the smallest doll, you open one doll to reveal a smaller one inside, and repeat — until you reach the smallest doll that doesn't open any further. That smallest doll is the base case.

Examples

Factorial using recursion

function factorial(n) {
  if (n <= 1) return 1;       // base case
  return n * factorial(n - 1); // recursive case
}

console.log(factorial(4)); // 4 * 3 * 2 * 1 = 24

Each call reduces n by 1 and calls itself again, until n reaches 1 — the base case — at which point the calls start returning back up the chain.

How it works

Each call to a recursive function is placed on the call stack, waiting for the call it made to finish and return a value. Once the base case is reached, the calls resolve in reverse order — like unwinding a stack of plates — each one multiplying or combining its result with what it gets back, until the original call finally returns.

factorial(4)
  → 4 * factorial(3)
       → 3 * factorial(2)
            → 2 * factorial(1)
                 → returns 1 (base case)
            → returns 2 * 1 = 2
       → returns 3 * 2 = 6
  → returns 4 * 6 = 24

Why does it exist?

Some structures and problems (folders inside folders, trees, certain mathematical definitions) are naturally recursive — describing them without recursion often requires extra bookkeeping that a recursive function handles automatically through the call stack.

When to use it

Reach for recursion when a problem is naturally defined in terms of a smaller version of itself — traversing nested folders, walking a tree, or classic divide-and-conquer algorithms like merge sort.

When not to use it

For a problem that's really just "do this N times in a row" (like summing a flat array), a loop is usually clearer and avoids the memory cost of piling up function calls on the stack. Watch recursion depth on very large inputs — too many nested calls can overflow the call stack.

Common mistakes

  • Forgetting the base case, causing infinite recursion until the program crashes ('stack overflow').

  • Writing a recursive case that doesn't actually move closer to the base case.

  • Using recursion for a simple problem a loop would solve more efficiently and clearly.

Practice exercises

  1. Easy:

    Write a recursive function that sums all numbers from 1 to n.

  2. Medium:

    Write a recursive function that reverses a string.

  3. Hard:

    Write a recursive function that returns all subsets of a given array.

Interview questions

What two things does every recursive function need?

A base case that stops the recursion, and a recursive step that moves the input closer to that base case.

What causes a 'stack overflow' in recursion?

Recursing too deeply (or infinitely, due to a missing/broken base case) fills up the call stack beyond its limit.

When would you prefer recursion over a loop?

When the problem is naturally recursive in structure — like traversing trees, nested data, or divide-and-conquer algorithms — where recursion reads more clearly than manual bookkeeping.

Trace `factorial(4)` step by step, showing both the 'calling down' and 'returning up' phases.

Calling down: factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1), which hits the base case and returns 1 without calling further. Returning up: factorial(2) computes 2 * 1 = 2 and returns it; factorial(3) computes 3 * 2 = 6 and returns it; factorial(4) computes 4 * 6 = 24 and returns it as the final answer.

What is the time and space complexity of the recursive factorial function, and where does the space cost come from?

O(n) time, since there are exactly n calls before reaching the base case. O(n) space, but not for the values being computed — it's the call stack: each pending call stays on the stack until the calls beneath it return, so n frames are alive simultaneously at the deepest point.

Why does the iterative version of factorial only need O(1) extra space, while the recursive version needs O(n)?

The iterative version keeps a single running total and loop counter, updating them in place — no history of previous steps needs to be remembered. The recursive version has to keep every pending call's stack frame (with its own n and pending multiplication) alive until deeper calls resolve, so memory usage grows with recursion depth.

What is tail recursion, and does JavaScript automatically optimize it away like some other languages do?

A recursive call is in tail position when it's the very last thing the function does — no pending work (like a multiplication) is left to perform after it returns. Some languages/engines implement 'proper tail calls,' reusing the current stack frame instead of pushing a new one, turning tail recursion into O(1) stack space. The ECMAScript 2015 spec includes proper tail calls, but in practice most JavaScript engines — including V8 (Chrome/Node.js) — never shipped it; only Safari's JavaScriptCore does. So writing tail-recursive JavaScript does not reliably avoid stack growth the way it would in a language that guarantees the optimization.

Rewrite `factorial` to be tail-recursive using an accumulator parameter, and explain why the rewritten version qualifies as tail-recursive but the original doesn't.

function factorial(n, acc = 1) { if (n <= 1) return acc; return factorial(n - 1, n * acc); }. The original (return n * factorial(n - 1)) has a pending multiplication waiting on the recursive call to return, so the recursive call isn't the last action — the multiply happens after it. The rewrite passes the running product forward as acc and does nothing after the recursive call returns except hand its result straight back.

Given that most JavaScript engines don't implement proper tail calls, does making a function tail-recursive actually save it from stack overflow in Node.js?

No — without engine support, a tail-recursive call in Node.js/V8 still pushes a new stack frame just like any other recursive call, so a deep tail-recursive call can still overflow the stack. The rewrite is stylistically cleaner and would get the optimization on an engine that implements it (like Safari), but it isn't a guaranteed fix in most JavaScript runtimes.

What is trampolining, and how does it let you simulate tail-call optimization manually in a language without it?

Instead of calling itself directly, each recursive step returns a thunk (a zero-argument function representing the next step) rather than invoking it immediately. A driving loop (the 'trampoline') repeatedly calls whatever thunk it's handed until a real value, not a function, comes back. Because each step returns to the trampoline's loop instead of recursing, the call stack never grows with the number of steps — only one frame is ever on the stack at a time.

What is memoization, and how does it change the time complexity of computing the nth Fibonacci number recursively?

Memoization caches a call's result keyed by its input, so a repeated call with the same input returns the cached result instead of recomputing it. Naive recursive Fibonacci recomputes the same subproblems repeatedly (fib(5) calls fib(3) twice, fib(2) three times, and so on), growing exponentially — commonly cited as O(2^n), though the tighter bound is O(φⁿ) ≈ O(1.618ⁿ). With memoization, each distinct fib(k) from 0 to n is computed exactly once, dropping the time to O(n), at the cost of O(n) extra space for the cache.

Why is naive recursive Fibonacci exponential, when the function only ever calls itself twice per invocation?

Each call to fib(n) spawns two more calls, fib(n-1) and fib(n-2), and both of those spawn two more, and so on — the number of calls roughly doubles with each additional level of depth, over roughly n levels, giving exponential growth (commonly bounded as O(2^n)). Critically, many of those calls compute the exact same subproblem repeatedly — e.g. fib(n-2) is reached both directly from fib(n) and indirectly via fib(n-1) — which is exactly the redundant work memoization eliminates.

What's the difference between 'linear recursion' (like factorial) and 'tree recursion' (like naive Fibonacci) in terms of the shape of the call graph, and how does that affect complexity?

Linear recursion makes exactly one recursive call per invocation, so the call graph is a single chain of depth n — time complexity is typically O(n). Tree recursion makes more than one recursive call per invocation, so the call graph branches into a tree — the total number of calls grows with the number of nodes in that tree, often exponential in the input size unless the subproblems overlap and get memoized.

What is the recurrence relation for merge sort's time complexity, and what does it evaluate to?

T(n) = 2T(n/2) + O(n) — each call splits the input into two halves (recursing on each) and then does O(n) work merging the results back together. By the Master Theorem, this resolves to O(n log n).

What is the recurrence relation for a function like binary search's time complexity, and why does it resolve to O(log n) instead of O(n)?

T(n) = T(n/2) + O(1) — each call does a constant amount of work and recurses into only one half of the remaining input, discarding the other half entirely. Because the problem size shrinks by half each time but only one branch is explored (unlike merge sort's two), the number of times n can be halved before reaching 1 is log₂(n), giving O(log n) total.

What is divide-and-conquer, and how does recursion make it a natural fit?

Divide-and-conquer solves a problem by splitting it into smaller subproblems of the same shape, solving each one (usually recursively), and combining their results into the overall answer. Recursion maps directly onto this: the 'divide' step becomes the recursive calls on smaller inputs, and the base case is the smallest subproblem simple enough to solve directly — the call stack tracks pending subproblems automatically.

Why is recursion a natural fit for traversing a tree, but breadth-first traversal is conventionally written iteratively with an explicit queue instead?

A tree is itself a recursively-defined structure (a node plus subtrees, which are themselves nodes plus subtrees), so depth-first recursion — process this node, then recurse into each child — mirrors that definition directly, with the call stack tracking the path back up. Breadth-first traversal needs to visit nodes level by level across different branches, which doesn't correspond to a single call chain going deeper — it needs an explicit FIFO queue of discovered-but-not-yet-visited nodes, which recursion's LIFO call stack doesn't provide for free.

What is mutual (indirect) recursion? Give an example.

Two or more functions that call each other rather than themselves directly — function A calls function B, which calls function A again, and so on, until some base case stops the chain. A classic example: isEven(n) returns true if n === 0, else returns isOdd(n - 1); isOdd(n) returns false if n === 0, else returns isEven(n - 1) — neither calls itself directly, but together they recurse.

What's the subtle bug in `function sum(arr) { if (arr.length === 0) return 0; sum(arr.slice(1)) + arr[0]; }`?

The recursive call's result is never returned — the line computes a value and discards it, since there's no return keyword. The function implicitly returns undefined in every case except the empty-array base case, so any call on a non-empty array returns undefined instead of the sum.

Roughly how many stack frames can a JavaScript call stack hold before overflowing, and what does that mean for recursion on very large inputs?

It varies by engine and available stack memory, but typically somewhere from a few thousand up to around ten-to-fifteen thousand frames for ordinary functions in Node.js/V8. This means naive recursion over a very large input — one recursive call per element of, say, a million-element array — will overflow the stack long before finishing, even though the same task would run fine as a simple loop.

Why is a loop generally preferred over recursion for a simple 'do this for every item' task, even though both can technically solve it?

A loop uses a fixed, constant amount of stack space regardless of item count (O(1) extra space), while recursion adds a new stack frame per call (O(n) extra space) and risks overflowing on large inputs. For a problem with no natural recursive substructure — it's just repetition, not 'a smaller version of the same problem' — recursion adds this cost without buying anything in return.

How would you convert an iterative loop that accumulates a total into a recursive function producing the same result?

Pass the running total (and current position) as parameters, updating them the way the loop body would, and recurse forward instead of looping: function sumFrom(arr, i = 0, total = 0) { if (i === arr.length) return total; return sumFrom(arr, i + 1, total + arr[i]); }. The base case is running off the end of the array, and each call carries the accumulated state forward as arguments instead of as loop-local variables.

What is backtracking, and how does it relate to plain recursion?

Backtracking is recursion with an added discipline: at each step, try a choice, recurse into the consequences of that choice, and if it doesn't lead to a valid solution, undo the choice and try the next one — pruning branches that can't possibly work rather than exploring the entire search tree unconditionally. It's used for problems like generating permutations, solving Sudoku, or N-Queens.

What's the time complexity of a recursive function that generates all subsets of an n-element array, and why?

O(2^n), because there are exactly 2^n possible subsets of an n-element set (each element is either included or excluded, independently), and any correct algorithm must at minimum produce all of them — the recursion branches into two calls (include / exclude the current element) at each of the n elements.

What's the time complexity of a recursive function that generates all permutations of an n-element array, and why is it worse than the subset-generation recursion?

O(n!), since there are n! distinct orderings of n elements, and generating each one requires the recursion to branch into a shrinking number of remaining choices at each of n levels rather than a fixed 2 — n! grows dramatically faster than 2^n as n increases, making permutation generation intractable for even moderately large n where subset generation might still be feasible.

Why does recursion make sense for traversing nested folders/JSON but not for looping over a flat array of numbers?

Nested folders are recursively self-similar — a folder contains files and other folders, which are themselves folders containing files and folders — so a function that processes 'this folder, then each subfolder the same way' matches the data's own shape, and the nesting depth isn't known in advance. A flat array has no such recursive substructure — it's just a fixed sequence to step through once — so a simple loop already matches its shape without needing the call stack's help.

Trace the call tree for `fib(4)` under naive (non-memoized) recursion, and count how many times `fib(1)` gets computed.

fib(4) calls fib(3) and fib(2). fib(3) calls fib(2) and fib(1). That first fib(2) calls fib(1) and fib(0). The fib(2) called directly from fib(4) calls its own fib(1) and fib(0). In total, fib(1) is computed 3 times and fib(0) 2 times across the tree — the same base-case subproblems recomputed repeatedly, exactly the redundant work memoization eliminates.

What's the extra space cost of the memoization cache itself in top-down (recursive) dynamic programming, on top of the call stack?

O(n) (or however many distinct subproblems exist), since the cache needs one entry per distinct input the recursion is ever called with — for Fibonacci, one entry per integer from 0 to n. This is in addition to, not instead of, the O(n) call stack depth the recursion still uses.

How would you decide whether a recursive solution should make one recursive call, two, or more, just from how the problem is worded?

Look at how many smaller subproblems the problem's own definition naturally splits into. If solving it requires combining the answer from exactly one smaller instance (like 'the sum of everything after the first element'), one recursive call suffices. If it requires combining results from multiple smaller instances (like Fibonacci's 'sum of the previous two,' or exploring 'include or exclude this item'), the number of calls should mirror the number of smaller subproblems the definition itself refers to.

Why can two functions that are both 'O(n) recursive calls deep' have very different actual running times?

Recursion depth only measures how many nested calls are pending at once — it says nothing about how much work happens at each level, or how many sibling calls happen at each level. A linear-recursive function doing O(1) work per call and a tree-recursive function branching into two calls per level can both have a deepest chain of n calls, yet the tree-recursive one does exponentially more total work because of the sibling branches at each level, not just the depth of one chain.

A recursive function meant to reduce the problem size still infinitely recurses even though the recursive call is present. What's usually wrong?

The argument passed to the recursive call doesn't actually get smaller (or closer to the base case) — e.g. calling recurse(n) again instead of recurse(n - 1), or slicing the wrong end of an array — so every call sees the same input as its caller and the base case is never reached, no matter how many times it recurses.

Scenario: a recursive function correctly returns the right answer for small inputs during testing, but crashes in production. What are the two most likely explanations, in order of likelihood?

Most likely, the production input is simply much larger/deeper than anything tested, and the recursion depth exceeds the call stack limit (stack overflow) even though the logic is correct. Less commonly, there's an edge case in the untested input — an empty array, a negative number, a specific value that skips the base case — that the small test inputs never happened to exercise, causing infinite (or far deeper than expected) recursion.

What does it mean for a recursive algorithm to have 'overlapping subproblems,' and why is that specifically what makes memoization worthwhile?

It means the recursion calls itself with the same arguments more than once along different paths (like fib(n-2) being reached both directly and via fib(n-1)). Memoization only pays off when this happens — caching a result is wasted effort if every recursive call receives distinct arguments and is therefore only ever computed once anyway.

Why doesn't merge sort benefit from memoization the way naive Fibonacci does?

Merge sort's recursive calls each operate on a distinct, non-overlapping half of the array — mergeSort(arr[0..n/2]) and mergeSort(arr[n/2..n]) are never called again with the same input elsewhere in the recursion tree. Memoization only helps when subproblems recur; since merge sort's subproblems are all unique, there's nothing to cache and reuse.

Two recursive functions each solve an n-element problem: one recurses on `n - 1` (one smaller), the other recurses on `n / 2` (halved) — both making a single recursive call. Why is one typically O(n) and the other O(log n)?

Shrinking by a fixed amount (n - 1) means it takes n steps to reach the base case, giving O(n) calls. Shrinking by a fixed fraction (n / 2) means it only takes about log₂(n) halvings to reach the base case, giving O(log n) calls — the difference between subtracting and dividing compounds dramatically as n grows.