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

// 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.

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

// 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!