Home›Fundamental Problems›Recursion in Coding Interviews

Recursion in Coding Interviews

February 7, 20185 min readUpdated 8/13/2026

Most people can explain what recursion is and still freeze when a problem needs it under time pressure. This is not about the definition — for that, start with Recursion, which covers the mechanics and the call stack. This is about the part that actually gets tested: recognising a recursive problem, writing the function without tracing it in your head, and knowing when recursion is the wrong tool.

Three questions, in order

Every recursive function is the answer to the same three questions. Ask them explicitly, out loud, in this order — it turns a blank page into a fill-in-the-blanks exercise.

  1. What is the smallest input I can answer without thinking? That is the base case. Empty list, null node, n == 0.
  2. How do I make the problem smaller? One element off the front, one level down the tree, half the array. If nothing gets smaller, the recursion never ends.
  3. Given the answer for the smaller problem, how do I build mine? This is the recurrence, and it is the only part that needs real thought.

Write the base case first, always. It is the cheapest line in the function and the one whose absence causes a stack overflow rather than a wrong answer.

The leap of faith

Here is the habit that separates people who find recursion natural from people who find it painful.

Assume the recursive call already works. Do not trace it. When you write depth(node.left), treat it as a finished function written by somebody competent that returns the depth of the left subtree. Your only job is to combine that answer with depth(node.right) correctly.

Tracing three levels deep in your head is what makes recursion feel hard, and it does not scale past about two levels anyway. If the base case is right and the recurrence is right, the function is right — induction guarantees it, and you do not need to simulate the machine.

// Read this as: "the depth is one more than the deeper of my two children."
// Do not trace it. Trust the two calls.
private int depth(TreeNode node) {
    if (node == null) return 0;                              // 1. base case

    int left = depth(node.left);                             // 2. smaller problems
    int right = depth(node.right);

    return Math.max(left, right) + 1;                        // 3. combine
}

Recursion on a tree is the easy case

Trees are recursive structures — a tree is a node with two smaller trees hanging off it — so the code mirrors the data and the three questions answer themselves. If you want to get fluent quickly, do tree problems.

The pattern worth drilling is the one where the function must return one thing while recording another:

// Returns depth upwards; records the best answer seen anywhere along the way.
private int depth(TreeNode node) {
    if (node == null) return 0;

    int left = depth(node.left);
    int right = depth(node.right);

    best = Math.max(best, left + right);      // a path turning around HERE
    return Math.max(left, right) + 1;         // what my parent needs from me
}

That is Diameter of Binary Tree, and the identical skeleton solves Binary Tree Maximum Path Sum, Longest Univalue Path and Balanced Binary Tree. Learn it once.

When recursion is the wrong tool

Knowing when not to recurse is worth as much as knowing how.

Overlapping subproblems. Naive Fibonacci recomputes fib(30) millions of times and takes exponential time. The fix is not to abandon recursion — it is to cache:

// Exponential. fib(50) will not finish.
int fib(int n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

// Linear. One line's difference, and the shape is identical.
int fib(int n, Long[] memo) {
    if (n < 2) return n;
    if (memo[n] != null) return memo[n].intValue();

    memo[n] = (long) (fib(n - 1, memo) + fib(n - 2, memo));
    return memo[n].intValue();
}

Use a boxed type in the cache so null can mean "not computed". With a primitive there is no way to distinguish an uncomputed entry from a computed 0 — the same reason Regular Expression Matching memoises with Boolean rather than boolean.

Memoised recursion is top-down dynamic programming. If you can write the recursion and spot the repeated arguments, you have already written the DP.

Depth. Every call is a stack frame. Recursing once per element over a 100,000-element linked list overflows the Java stack, and Python throws RecursionError past a default of 1000. When the depth is proportional to the input size rather than its logarithm, use an explicit stack or a loop. This is why Number of Islands sometimes needs BFS instead of DFS.

It is a plain loop. Summing an array recursively is not clever, it is slower and more fragile. Recursion earns its place when the structure branches — trees, graphs, and choices.

Backtracking: recursion that undoes itself

The other family you will meet. Build a partial answer, recurse, then undo the move so the next branch starts clean:

for (int i = start; i < candidates.length; i++) {
    path.add(candidates[i]);                       // choose
    backtrack(result, path, candidates, i, remaining - candidates[i]);   // explore
    path.remove(path.size() - 1);                  // UNDO
}

Forgetting the undo is the classic bug, and it is a quiet one — the output still looks plausible, just wrong. See Combination Sum and Generate Parentheses.

One more trap in that family: when you record a successful path, copy it. result.add(path) stores a reference to a list that keeps mutating, and you finish with a result full of identical empty lists.

Reasoning about cost

You will be asked. Two shortcuts cover most cases:

  • Halving the input each call — T(n) = T(n/2) + O(1) — is O(log n). Binary search.
  • Halving but visiting everything — T(n) = 2T(n/2) + O(n) — is O(n log n). Merge sort, Merge k Sorted Lists.

For branching searches, count the tree instead: branching factor to the power of the depth. Two choices at each of n steps is O(2ⁿ); picking one of n remaining items at each of n steps is O(n!).

Space is the maximum depth of the stack, not the number of calls — the frames of a finished branch are gone before the next one starts. That is why a tree recursion is O(h) and not O(n).

A checklist for the interview

  • Base case written first, and it handles null or empty.
  • Every recursive call is on something strictly smaller.
  • You stated what the function returns in one sentence before writing the body.
  • You trusted the recursive call instead of tracing it.
  • You checked for repeated arguments — if there are any, memoise.
  • If you are backtracking: you undo the move, and you copy the path into the result.
  • You know the maximum depth, and whether it is safe.