Recursion & Memoization

What is Recursion?

Recursion is when a function calls itself. It's a powerful technique for solving problems that can be broken down into smaller, identical subproblems. Every recursive function needs two things: a base case (when to stop) and a recursive case (when to call itself).

// Classic example: factorial
// 5! = 5 * 4 * 3 * 2 * 1 = 120
function factorial(n) {
  if (n <= 1) return 1;   // BASE CASE: stop here
  return n * factorial(n - 1);  // RECURSIVE CASE
}

// What happens for factorial(4):
// factorial(4) → 4 * factorial(3)
//                    → 3 * factorial(2)
//                            → 2 * factorial(1)
//                                    → 1 (base case)
//                            ← 2 * 1 = 2
//                    ← 3 * 2 = 6
//              ← 4 * 6 = 24

console.log(factorial(5));  // 120

// Fibonacci sequence:
// 0, 1, 1, 2, 3, 5, 8, 13, 21...
function fib(n) {
  if (n <= 1) return n;          // base cases: fib(0)=0, fib(1)=1
  return fib(n-1) + fib(n-2);   // recursive case
}
console.log(fib(10));  // 55

Practical Recursion

// Traverse nested data — recursion is perfect for trees
const fileSystem = {
  name: "root",
  children: [
    { name: "src", children: [
      { name: "index.js", children: [] },
      { name: "utils.js", children: [] }
    ]},
    { name: "tests", children: [
      { name: "test.js", children: [] }
    ]}
  ]
};

function printTree(node, indent = 0) {
  console.log(" ".repeat(indent * 2) + node.name);
  for (const child of node.children) {
    printTree(child, indent + 1);  // recursive call with increased indent
  }
}
printTree(fileSystem);

// Flatten a deeply nested array recursively:
function flatten(arr) {
  return arr.reduce((flat, item) => {
    return Array.isArray(item)
      ? flat.concat(flatten(item))  // recurse on nested arrays
      : flat.concat(item);          // base case: add primitive
  }, []);
}
console.log(flatten([1, [2, [3, [4]]]]));  // [1, 2, 3, 4]
// (Or use arr.flat(Infinity) built-in)

Memoization — Optimizing Recursion

// Problem: naive fib is very slow for large n
// fib(40) makes BILLIONS of redundant calls
function slowFib(n) {
  if (n <= 1) return n;
  return slowFib(n-1) + slowFib(n-2);  // repeated work!
}

// Memoization: cache results of calls we've already made
function memoFib() {
  const cache = {};
  return function fib(n) {
    if (n in cache) return cache[n];  // use cached result
    if (n <= 1) return n;
    cache[n] = fib(n-1) + fib(n-2);  // store before returning
    return cache[n];
  };
}

const fib = memoFib();
console.log(fib(50));   // Fast!
console.log(fib(100));  // Still fast!

// Generic memoize function:
function memoize(fn) {
  const cache = new Map();
  return function(...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}