How does recursion work in JavaScript?

// Classic example: factorial
// 5! = 5 × 4 × 3 × 2 × 1 = 120
function factorial(n: number): number {
  // Base case — stops the recursion
  if (n <= 1) return 1;

  // Recursive case — calls itself with smaller input
  return n * factorial(n - 1);
}

// How the call stack builds up:
// factorial(5)
//   → 5 * factorial(4)
//     → 4 * factorial(3)
//       → 3 * factorial(2)
//         → 2 * factorial(1)
//           → 1 (base case hit!)
//         → 2 * 1 = 2
//       → 3 * 2 = 6
//     → 4 * 6 = 24
//   → 5 * 24 = 120

// Each call waits for the next one to return before it can compute its result
// The stack grows to depth n before unwinding

// Deep flatten an arbitrarily nested array
function deepFlatten<T>(arr: (T | T[])[]): T[] {
  const result: T[] = [];

  for (const item of arr) {
    if (Array.isArray(item)) {
      result.push(...deepFlatten(item)); // Recurse into nested arrays
    } else {
      result.push(item); // Base case: not an array
    }
  }

  return result;
}

deepFlatten([1, [2, [3, [4, 5]]], 6]); // [1, 2, 3, 4, 5, 6]

// Sum all values in a nested object (any depth)
function deepSum(obj: Record<string, unknown>): number {
  let total = 0;

  for (const value of Object.values(obj)) {
    if (typeof value === 'number') {
      total += value; // Base case: it's a number
    } else if (typeof value === 'object' && value !== null) {
      total += deepSum(value as Record<string, unknown>); // Recurse
    }
  }

  return total;
}

deepSum({ a: 1, b: { c: 2, d: { e: 3 } }, f: 4 }); // 10

// Find a node in a tree
type TreeNode = { id: string; children: TreeNode[] };

function findNode(tree: TreeNode, targetId: string): TreeNode | null {
  if (tree.id === targetId) return tree; // Base case: found it

  for (const child of tree.children) {
    const found = findNode(child, targetId); // Recurse into children
    if (found) return found;
  }

  return null; // Not in this subtree
}

// Binary search — O(log n)
function binarySearch(arr: number[], target: number, low = 0, high = arr.length - 1): number {
  if (low > high) return -1; // Base case: not found

  const mid = Math.floor((low + high) / 2);

  if (arr[mid] === target) return mid;           // Base case: found
  if (arr[mid] < target) return binarySearch(arr, target, mid + 1, high); // Right half
  return binarySearch(arr, target, low, mid - 1); // Left half
}

// Merge sort — O(n log n)
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr; // Base case

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // Sort left half
  const right = mergeSort(arr.slice(mid));     // Sort right half

  return merge(left, right); // Combine sorted halves
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let leftIdx = 0;
  let rightIdx = 0;

  while (leftIdx < left.length && rightIdx < right.length) {
    if (left[leftIdx] <= right[rightIdx]) {
      result.push(left[leftIdx++]);
    } else {
      result.push(right[rightIdx++]);
    }
  }

  return [...result, ...left.slice(leftIdx), ...right.slice(rightIdx)];
}

// ❌ Stack overflow — no base case
function infinite(): number {
  return infinite(); // Never stops!
  // RangeError: Maximum call stack size exceeded
}

// ❌ Stack overflow — input too large for recursive approach
function sumTo(n: number): number {
  if (n <= 0) return 0;
  return n + sumTo(n - 1);
}
sumTo(100000); // Stack overflow! 100,000 frames deep

// ✅ Convert to iteration for large inputs
function sumToIterative(n: number): number {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}
sumToIterative(100000); // Works fine — no stack growth

// ✅ Tail-call form (optimized in Safari, not V8/SpiderMonkey)
function sumToTail(n: number, accumulator = 0): number {
  if (n <= 0) return accumulator;
  return sumToTail(n - 1, accumulator + n); // Tail position
  // In theory, engine can reuse the same stack frame
  // In practice, only Safari implements TCO
}

// ❌ Naive Fibonacci — O(2^n) time, recalculates everything
function fibNaive(n: number): number {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}
// fibNaive(40) takes several seconds!
// fibNaive(50) takes minutes!

// ✅ Memoized Fibonacci — O(n) time, each value computed once
function fibMemo(n: number, cache: Map<number, number> = new Map()): number {
  if (n <= 1) return n;
  if (cache.has(n)) return cache.get(n)!; // Already computed

  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  cache.set(n, result); // Store for future calls
  return result;
}
// fibMemo(50) returns instantly

// Generic memoize wrapper
function memoize<Args extends unknown[], Result>(
  fn: (...args: Args) => Result
): (...args: Args) => Result {
  const cache = new Map<string, Result>();

  return (...args: Args): Result => {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key)!;

    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

const fib = memoize((n: number): number => {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
});