Common Recursion Patterns

Recursion looks magical until you recognize the handful of structural patterns that underlie virtually every recursive algorithm. Once you can identify the pattern, writing the solution becomes a matter of filling in the template.

There are six core recursion patterns. Master these and you will be able to solve new recursive problems by recognizing which template applies.

Pattern 1: Linear Recursion

Each call makes exactly one recursive call. The call tree is a straight chain. Time complexity: O(n). Space: O(n) stack frames.

// Template: do work, then recurse (or recurse, then do work)
// Call chain: f(n) → f(n-1) → f(n-2) → ... → f(0)

// Sum of array elements
function sumArray(arr, i = 0) {
  if (i === arr.length) return 0;     // base case
  return arr[i] + sumArray(arr, i + 1);  // 1 recursive call
}

// Find maximum in array
function findMax(arr, i = 0) {
  if (i === arr.length - 1) return arr[i];  // base case
  return Math.max(arr[i], findMax(arr, i + 1));
}

// Check if array is palindrome
function isPalindrome(s, lo = 0, hi = s.length - 1) {
  if (lo >= hi) return true;
  if (s[lo] !== s[hi]) return false;
  return isPalindrome(s, lo + 1, hi - 1);  // 1 recursive call
}

// Power function: x^n
function power(x, n) {
  if (n === 0) return 1;
  return x * power(x, n - 1);   // O(n) — could be O(log n) with binary recursion
}

Pattern 2: Binary Recursion

Each call makes exactly two recursive calls. The call tree is a binary tree. Classic examples: binary search (implicit), merge sort, tree traversal.

When each subproblem is HALF the size and work at each level sums to O(n): O(n log n) total. When each call does O(1) work and makes 2 full-size calls: O(2^n) total.

// Divide and conquer sum — 2 calls, each on half the array
function sumDivide(arr, lo = 0, hi = arr.length - 1) {
  if (lo === hi) return arr[lo];   // base case: single element
  const mid = Math.floor((lo + hi) / 2);
  return sumDivide(arr, lo, mid) + sumDivide(arr, mid + 1, hi);
  // T(n) = 2T(n/2) + O(1) → O(n) by Master Theorem
}

// Fast power: x^n using binary recursion — O(log n) instead of O(n)
function fastPower(x, n) {
  if (n === 0) return 1;
  const half = fastPower(x, Math.floor(n / 2));  // solve subproblem once
  if (n % 2 === 0) return half * half;           // even exponent
  return x * half * half;                        // odd exponent
  // T(n) = T(n/2) + O(1) → O(log n)
}

// Merge sort — 2 calls on halves, O(n) merge work
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);  // O(n) merge
  // T(n) = 2T(n/2) + O(n) → O(n log n)
}

Pattern 3: Multiple Recursion (Exponential Tree)

Each call makes more than two recursive calls, or the subproblems overlap (same subproblem computed multiple times). The naive call tree has exponential size. Memoization collapses overlapping subproblems.

// Naive Fibonacci — binary tree but subproblems OVERLAP heavily
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
  // fib(40) makes ~2.7 billion calls because fib(38) is computed twice,
  // fib(37) four times, fib(36) eight times, etc.
  // Time: O(2^n), Space: O(n) stack
}

// Naive Fibonacci call tree for fib(5):
//              fib(5)
//           /          //       fib(4)         fib(3)
//      /             /     //   fib(3)  fib(2) fib(2) fib(1)
//   /      /     /   // fib(2) fib(1) ...   (fib(2) and fib(3) computed multiple times!)

// Memoized — each unique subproblem solved ONCE: O(n) time, O(n) space
function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

// Tribonacci — 3 recursive calls, O(3^n) without memoization
function trib(n, memo = new Map()) {
  if (n <= 0) return 0;
  if (n === 1) return 1;
  if (memo.has(n)) return memo.get(n);
  const result = trib(n-1, memo) + trib(n-2, memo) + trib(n-3, memo);
  memo.set(n, result);
  return result;
}

Pattern 4: Divide and Conquer

Break the problem into independent subproblems, solve each recursively, then combine results. The subproblems do NOT overlap (unlike DP). The combination step is key to the algorithm's power.

// Template:
// function solve(problem) {
//   if (small enough) return base_case;
//   left = solve(left_half);
//   right = solve(right_half);
//   return combine(left, right);
// }

// Maximum subarray (divide and conquer variant of Kadane's)
function maxSubarray(arr, lo = 0, hi = arr.length - 1) {
  if (lo === hi) return arr[lo];
  const mid = Math.floor((lo + hi) / 2);

  // Best subarray entirely in left half
  const leftMax = maxSubarray(arr, lo, mid);
  // Best subarray entirely in right half
  const rightMax = maxSubarray(arr, mid + 1, hi);
  // Best subarray crossing the midpoint
  const crossMax = maxCrossing(arr, lo, mid, hi);

  return Math.max(leftMax, rightMax, crossMax);  // combine
}

function maxCrossing(arr, lo, mid, hi) {
  let leftSum = -Infinity, sum = 0;
  for (let i = mid; i >= lo; i--) { sum += arr[i]; leftSum = Math.max(leftSum, sum); }
  let rightSum = -Infinity; sum = 0;
  for (let i = mid + 1; i <= hi; i++) { sum += arr[i]; rightSum = Math.max(rightSum, sum); }
  return leftSum + rightSum;
}
// T(n) = 2T(n/2) + O(n) → O(n log n)
// Note: Kadane's algorithm solves this in O(n) — D&C is elegant but not optimal here

// Count inversions (number of pairs i<j where arr[i] > arr[j])
function countInversions(arr) {
  if (arr.length <= 1) return { sorted: arr, count: 0 };
  const mid = Math.floor(arr.length / 2);
  const { sorted: left, count: leftCount } = countInversions(arr.slice(0, mid));
  const { sorted: right, count: rightCount } = countInversions(arr.slice(mid));
  const { merged, count: splitCount } = mergeCount(left, right);
  return { sorted: merged, count: leftCount + rightCount + splitCount };
}

function mergeCount(left, right) {
  let merged = [], count = 0, i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) { merged.push(left[i++]); }
    else { merged.push(right[j++]); count += left.length - i; }  // all remaining left elements > right[j]
  }
  return { merged: merged.concat(left.slice(i)).concat(right.slice(j)), count };
}

Pattern 5: Generate All (Backtracking)

Explore all possible solutions by building candidates incrementally. At each step, either extend the current candidate or backtrack and try a different choice. Time complexity is often O(n!) or O(2^n) because you enumerate all possibilities.

// Generate all subsets of an array (2^n subsets)
function subsets(nums) {
  const result = [];
  function backtrack(start, current) {
    result.push([...current]);          // add current subset to results
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);            // choose nums[i]
      backtrack(i + 1, current);        // explore with nums[i] included
      current.pop();                    // un-choose (backtrack)
    }
  }
  backtrack(0, []);
  return result;
}
// subsets([1,2,3]) → [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

// Generate all permutations (n! permutations)
function permutations(nums) {
  const result = [];
  function backtrack(current, remaining) {
    if (remaining.length === 0) { result.push([...current]); return; }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(current, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
      current.pop();
    }
  }
  backtrack([], nums);
  return result;
}
// permutations([1,2,3]) → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

// Generate all combinations of k elements
function combinations(nums, k) {
  const result = [];
  function backtrack(start, current) {
    if (current.length === k) { result.push([...current]); return; }
    for (let i = start; i < nums.length; i++) {
      if (nums.length - i < k - current.length) break;  // pruning: not enough elements left
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }
  backtrack(0, []);
  return result;
}

Pattern 6: Mutual Recursion

Two (or more) functions call each other. Each function handles part of the problem, delegating the rest to the other. This models naturally alternating or interleaved structures.

// Classic mutual recursion: even/odd using function delegation
function isEven(n) {
  if (n === 0) return true;
  return isOdd(n - 1);   // delegates to isOdd
}

function isOdd(n) {
  if (n === 0) return false;
  return isEven(n - 1);  // delegates back to isEven
}

// More practical: HTML parser (simplified)
// Each element type delegates to the appropriate handler
function parseElement(tokens) {
  if (tokens[0] === 'text') return parseText(tokens);
  if (tokens[0] === '<') return parseTag(tokens);
  throw new Error(`Unknown token: ${tokens[0]}`);
}

function parseTag(tokens) {
  const tag = tokens[1];
  tokens.splice(0, 2);  // consume the opening tag
  const children = [];
  while (tokens.length && tokens[0] !== `</${tag}>`) {
    children.push(parseElement(tokens));  // mutual call
  }
  tokens.shift();  // consume closing tag
  return { type: 'element', tag, children };
}

function parseText(tokens) {
  const text = tokens.shift();
  return { type: 'text', content: text };
}

// Grammar-driven mutual recursion (expression parser)
// expr → term ('+' term)*
// term → factor ('*' factor)*
// factor → number | '(' expr ')'
// This mutual recursion naturally handles operator precedence!

Pattern Comparison

Pattern	Calls per Level	Typical Time	Key Technique
Linear	1	O(n)	Accumulator for tail recursion
Binary (halving)	2, n/2 each	O(n log n)	Merge/combine step
Binary (overlapping)	2, n-1 each	O(2^n) naive	Memoization → O(n)
Divide & Conquer	2+, n/b each	O(n log n)	Independent subproblems
Generate All	Branching factor	O(2^n) or O(n!)	Pruning, backtracking
Mutual	Alternating	Varies	Natural for interleaved structures

Tip

When you see a recursive problem, ask: "how many recursive calls does each function make, and how much smaller is each subproblem?" That answer tells you the pattern and the complexity. Binary + halving = O(n log n). Two calls + n-1 size = O(2^n), use memoization.

Note

Backtracking (generate all) is not just for enumeration problems. It is also the basis of constraint satisfaction solvers, Sudoku solvers, and many NP-complete approximations. The pruning step — returning early when a partial solution cannot lead to a valid complete solution — is what separates practical backtracking from brute force.