Algorithms Lesson 11: Recursion

Recursion is a function calling itself. Many problems that seem complex with loops become elegant with recursion. Trees and graphs naturally use recursion.

How Recursion Works

// Every recursive function needs:
// 1. Base case (stops recursion)
// 2. Recursive case (breaks problem down)

function factorial(n) {
  if (n <= 1) return 1;     // base case
  return n * factorial(n - 1); // recursive case
}
// factorial(4) = 4 * factorial(3)
//              = 4 * 3 * factorial(2)
//              = 4 * 3 * 2 * factorial(1)
//              = 4 * 3 * 2 * 1 = 24

function fibonacci(n) {
  if (n <= 1) return n;                 // base cases: fib(0)=0, fib(1)=1
  return fibonacci(n-1) + fibonacci(n-2); // O(2^n) — terrible!
}

// Memoized fibonacci: O(n)
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
  return memo[n];
}

Tree of Recursion

// Power set: all subsets of an array
function powerSet(arr) {
  if (arr.length === 0) return [[]];
  const [first, ...rest] = arr;
  const withoutFirst = powerSet(rest);
  const withFirst = withoutFirst.map(subset => [first, ...subset]);
  return [...withoutFirst, ...withFirst];
}
// powerSet([1,2,3]) → [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]