Recursion Explained: From Base Cases to Tree Traversal to Dynamic Programming

Recursion is one of the concepts that separates developers who struggle with algorithms from those who breeze through them. The mental model is simple once it clicks: a function that calls itself on a smaller version of the problem, until the problem is small enough to answer directly. This guide builds from that foundation all the way to dynamic programming.

⚡ TL;DR: Every recursive function needs: a base case (when to stop) and a recursive case (smaller subproblem). The call stack handles the “bookkeeping.” Memoization converts O(2ⁿ) recursive solutions to O(n). Bottom-up DP often avoids the call stack entirely.

The mental model — trust the recursion

// Factorial: n! = n * (n-1)!
// Base case: 0! = 1
// Recursive case: n! = n * factorial(n-1)

function factorial(n) {
  if (n === 0) return 1;               // Base case: stop here
  return n * factorial(n - 1);         // Recursive case: smaller problem
}

// factorial(4):
// 4 * factorial(3)
// 4 * 3 * factorial(2)
// 4 * 3 * 2 * factorial(1)
// 4 * 3 * 2 * 1 * factorial(0)
// 4 * 3 * 2 * 1 * 1 = 24

// Mental model:
// "Assume factorial(n-1) already works correctly.
// How do I use it to compute factorial(n)?"
// Trust the recursion to handle smaller cases.

Tree traversal — where recursion shines

const tree = {
  value: 1,
  left: { value: 2, left: { value: 4, left: null, right: null },
                     right: { value: 5, left: null, right: null } },
  right: { value: 3, left: null, right: { value: 6, left: null, right: null } }
};

// In-order (left, root, right) — gives sorted order for BST
function inOrder(node) {
  if (!node) return [];                    // Base case: empty node
  return [...inOrder(node.left), node.value, ...inOrder(node.right)];
}
inOrder(tree); // [4, 2, 5, 1, 3, 6]

// Tree depth:
function maxDepth(node) {
  if (!node) return 0;                     // Base case
  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

// Sum all nodes:
function treeSum(node) {
  if (!node) return 0;
  return node.value + treeSum(node.left) + treeSum(node.right);
}
// Recursion is the natural fit for trees — the structure IS recursive

Memoization — from O(2ⁿ) to O(n)

// Naive Fibonacci: O(2ⁿ) — exponential!
function fib(n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2); // Recomputes same values millions of times
}
// fib(40): ~2^40 = 1 trillion operations

// Memoized: O(n) — each value computed once
function fibMemo(n, cache = new Map()) {
  if (n <= 1) return n;
  if (cache.has(n)) return cache.get(n);  // Cache hit: skip computation
  const result = fibMemo(n-1, cache) + fibMemo(n-2, cache);
  cache.set(n, result);                   // Store before returning
  return result;
}
// fibMemo(1000): 1000 operations

// Bottom-up DP: same O(n) without call stack overhead
function fibDP(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];
  return curr;
} // O(1) space!

5 common recursive patterns

• Divide and conquer: split problem in half, solve each half recursively (merge sort, binary search)
• Tree traversal: visit each node exactly once (DFS inorder/preorder/postorder)
• Backtracking: try all possibilities, undo when stuck (N-Queens, maze solving, permutations)
• Memoized recursion (top-down DP): recursion + cache (Fibonacci, coin change, longest subsequence)
• Mutual recursion: function A calls function B which calls function A (parsing grammars, state machines)

Recursion is the foundation of the Big O analysis for tree algorithms — recognizing T(n) = 2T(n/2) + O(n) as O(n log n) is a core skill. External reference: VisuAlgo Recursion Visualization.