Recursion fundamentals

Overview

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every recursive function has two parts: a base case that returns an answer directly, and a recursive case that reduces the problem and trusts the recursive call to solve the smaller piece.

Recursion is the foundation for tree and graph traversal, backtracking, divide and conquer, and dynamic programming. The key mental shift is to stop tracing every call and instead trust the function's definition: if sum(arr, i) returns the sum from index i onward, then sum(arr, 0) = arr[0] + sum(arr, 1).

When to use it

• The data is recursive: trees, nested lists, file systems, JSON.
• The problem is naturally defined in terms of smaller versions of itself (factorial, Fibonacci, power).
• You need to explore choices: subsets, permutations, paths (backtracking).
• You can split the input into independent halves (merge sort, quicksort).

Problem patterns it solves

Where it is used in real software

Key terms

Base case

The smallest input answered directly without another call. Without it, recursion never stops.

Recursive case

The part that reduces the problem and calls the function again.

Call stack

The runtime stack of active function calls. Each call waits for its child to return.

Stack overflow

Error when recursion depth exceeds the stack limit (often around 10,000 frames in JS).

Leap of faith

Assume the recursive call correctly solves the smaller problem; only verify how you use its result.

How to write any recursive function

1. 1
   Define the function in one sentence

   Example: sum(arr, i) returns the sum of arr[i..end]. Be precise about inputs and what is returned.

2. 2
   Find the base case

   What is the smallest input? When i === arr.length, the remaining sum is 0.

3. 3
   Make the problem smaller

   Reduce toward the base case: i + 1, n - 1, n / 2, node.left.

4. 4
   Combine using the definition

   Trust sum(arr, i + 1) and use it: arr[i] + sum(arr, i + 1).

5. 5
   Check progress and termination

   Every call must move closer to the base case, or it will loop forever.

Trace of fibonacci(4) without memoization

fib(n) = fib(n - 1) + fib(n - 2), fib(0) = 0, fib(1) = 1

fib(2) is computed twice already at n = 4, and the duplication doubles with each level, giving O(2^n) calls. Caching results (memoization) reduces this to O(n) and is the bridge to dynamic programming.

Implementation

1// Linear recursion2function factorial(n) {3  if (n <= 1) return 1;          // base case4  return n * factorial(n - 1);   // smaller problem5}6 7// Recursion on an index instead of slicing (slice would copy: O(n^2))8function isPalindrome(s, left = 0, right = s.length - 1) {9  if (left >= right) return true;10  if (s[left] !== s[right]) return false;11  return isPalindrome(s, left + 1, right - 1);12}13 14// Divide in half: O(log n) calls15function power(x, n) {16  if (n === 0) return 1;17  if (n < 0) return 1 / power(x, -n);18  const half = power(x, Math.floor(n / 2));19  return n % 2 === 0 ? half * half : half * half * x;20}21 22// Tree recursion with memoization: O(2^n) becomes O(n)23function fib(n, memo = new Map()) {24  if (n <= 1) return n;25  if (memo.has(n)) return memo.get(n);26  const value = fib(n - 1, memo) + fib(n - 2, memo);27  memo.set(n, value);28  return value;29}30 31// Generate strings with constraints32function generateParenthesis(n) {33  const result = [];34  function build(current, open, close) {35    if (current.length === 2 * n) {36      result.push(current);37      return;38    }39    if (open < n) build(current + "(", open + 1, close);40    if (close < open) build(current + ")", open, close + 1);41  }42  build("", 0, 0);43  return result;44}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Missing or wrong base case.

  Fix: Test the smallest inputs first: empty array, n = 0, null node.

• Not returning the recursive result.

  Fix: Write return f(n - 1) rather than just calling f(n - 1).

• Sharing a mutable list without undoing changes.

  Fix: Push before the call and pop after it (backtracking), or pass a copy when recording a result.

• Tracing every call in your head.

  Fix: Trust the definition for the smaller problem and verify only the current level.

Interview questions

Practice problems