Recursion and backtracking explained

Recursion means a function calls itself on a smaller version of the problem until it reaches a case simple enough to answer directly. Backtracking builds on it: try a choice, explore, and undo the choice to try the next one. Both appear constantly in interviews and in real code that walks trees, folders and graphs.

The two parts of every recursive function

Base case: the simplest input, answered directly. It stops the recursion.
Recursive case: reduce the problem to a smaller one, call yourself, and combine the result.

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

If there is no base case, or the problem does not get smaller, the function never ends and you get a stack overflow.

The call stack

Each call gets its own frame on the call stack holding its variables. The calls pile up until the base case, then return one by one. That means recursion uses O(depth) memory. Very deep recursion (for example 100,000 levels) can crash, so for long chains consider a loop or an explicit stack.

A way to think recursively

Do not trace every call in your head. Use trust:

Define clearly what the function returns for any input.
Assume it works correctly for smaller inputs (the "recursive leap of faith").
Write how to solve the current input using those answers.
Add the base cases.

Example: sum of a list. sum(list) = first element + sum(rest); base case: empty list gives 0.

Overlapping work and memoization

Naive recursion can repeat work. The classic example:

function fib(n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }   // O(2^n)

fib(30) recomputes the same values many times. Memoization stores results already computed:

function fib(n, memo = new Map()) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const value = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);
  return value;
}
// O(n) time, O(n) space

Recursion plus memoization is the heart of dynamic programming (the topic of a later article).

Recursion on trees

Trees are naturally recursive: a tree is a node with smaller trees as children.

function height(node) {
  if (node === null) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

Backtracking: the template

Backtracking explores all possible choices in a decision tree, but abandons a path as soon as it cannot lead to a valid answer (pruning).

function backtrack(state, choices, results) {
  if (isComplete(state)) {
    results.push(copy(state));
    return;
  }
  for (const choice of choices) {
    if (!isValid(state, choice)) continue;   // prune
    apply(state, choice);                    // choose
    backtrack(state, nextChoices, results);  // explore
    undo(state, choice);                     // un-choose (backtrack)
  }
}

The three steps are choose, explore, un-choose.

Example 1: subsets

function subsets(nums) {
  const results = [], current = [];
  function go(start) {
    results.push([...current]);              // every path is a valid subset
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);                 // choose
      go(i + 1);                             // explore
      current.pop();                         // un-choose
    }
  }
  go(0);
  return results;
}
// 2^n subsets, so O(n * 2^n) time

Example 2: permutations

function permutations(nums) {
  const results = [], current = [], used = new Array(nums.length).fill(false);
  function go() {
    if (current.length === nums.length) { results.push([...current]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; current.push(nums[i]);
      go();
      current.pop(); used[i] = false;
    }
  }
  go();
  return results;
}
// n! permutations

Handling duplicates

When the input has repeated values and you want unique results, sort first and skip a value equal to the previous one at the same level (if (i > start && nums[i] === nums[i - 1]) continue;).

Complexity

Backtracking is often exponential: subsets O(2ⁿ), permutations O(n!). That is acceptable only for small n (usually up to about 20 for subsets, 10 for permutations). Pruning invalid branches early makes a big practical difference. If subproblems repeat, switch to memoization or dynamic programming.

Common mistakes

Missing or wrong base case, causing infinite recursion.
Pushing the same array reference into results instead of a copy.
Forgetting to undo a choice.
Not pruning, and exploring huge useless branches.
Using recursion where a simple loop is clearer and safer.

Practice problems

Fibonacci with memo, Power of a number, Reverse a linked list recursively, Subsets, Permutations, Combination Sum, Generate Parentheses, Word Search, N-Queens.

Takeaway: write the base case and the smaller-problem step, trust the recursion, and use choose-explore-undo for backtracking. Prune early and add memoization when work repeats.

Interview prep and DSA series, Part 1 (core patterns): 5 of 5. Previous: Binary search: patterns, templates and common pitfalls.

Recursion and backtracking explained with simple examples