1.20.g — Recursion

In one sentence: Recursion is when a function calls itself to solve a problem by breaking it into smaller sub-problems, always requiring a base case to stop and a recursive case that moves toward that base — and understanding the call stack is key to debugging and avoiding stack overflows.

Navigation: ← 1.20.f — Practice Problems · 1.20 Overview

---

1. What is recursion?

Recursion is a technique where a function calls itself as part of its own execution. Instead of using a loop to repeat work, the function delegates a smaller version of the problem to another call of itself.

function countdown(n) {
  if (n <= 0) {
    console.log("Done!");
    return;
  }
  console.log(n);
  countdown(n - 1); // The function calls itself with a smaller input
}

countdown(5);
// 5
// 4
// 3
// 2
// 1
// Done!

Every recursive function has two essential parts:

• Base case — the condition that stops the recursion.
• Recursive case — the function calling itself with a "smaller" or "simpler" input.

---

2. Base case vs recursive case — CRITICAL

Base case

The base case is the exit condition. Without it, the function would call itself forever.

Recursive case

The recursive case reduces the problem, moving closer to the base case with each call.

function factorial(n) {
  // BASE CASE — stop here
  if (n <= 1) return 1;

  // RECURSIVE CASE — reduce n by 1 each time
  return n * factorial(n - 1);
}

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

Trace of factorial(5):

factorial(5)
  → 5 * factorial(4)
    → 4 * factorial(3)
      → 3 * factorial(2)
        → 2 * factorial(1)
          → 1              ← base case reached
        → 2 * 1 = 2
      → 3 * 2 = 6
    → 4 * 6 = 24
  → 5 * 24 = 120

---

3. The call stack during recursion

Every time a function is called, JavaScript pushes a new frame onto the call stack. Each frame holds the function's local variables and the return address. Recursive calls create multiple frames on the stack simultaneously.

Visualizing the stack for factorial(4)

Call stack grows DOWN (each indented level = one frame deeper):

┌─────────────────────────┐
│ factorial(4)             │  ← waiting for factorial(3)
│   n = 4                 │
├─────────────────────────┤
│ factorial(3)             │  ← waiting for factorial(2)
│   n = 3                 │
├─────────────────────────┤
│ factorial(2)             │  ← waiting for factorial(1)
│   n = 2                 │
├─────────────────────────┤
│ factorial(1)             │  ← BASE CASE: returns 1
│   n = 1                 │
└─────────────────────────┘

Then the stack UNWINDS:
  factorial(1) returns 1
  factorial(2) returns 2 * 1 = 2
  factorial(3) returns 3 * 2 = 6
  factorial(4) returns 4 * 6 = 24

Each frame waits for the one below it to return before it can compute its result.

---

4. Stack overflow — what causes it

The call stack has a limited size (typically thousands to tens of thousands of frames, depending on the engine and environment). If recursion goes too deep without hitting a base case, you get a stack overflow:

// INFINITE RECURSION — no base case
function oops() {
  return oops(); // calls itself forever
}

// oops(); // RangeError: Maximum call stack size exceeded

Common causes of stack overflow

Mistake	Example
Missing base case	No if to stop
Base case never reached	Recursive call does not move toward the base case
Wrong direction	Counting up when you should count down
Input too large	Even correct recursion with n = 1000000 can overflow

// BUG: n never reaches 0 because we ADD 1 instead of subtracting
function badCountdown(n) {
  if (n <= 0) return;
  console.log(n);
  badCountdown(n + 1); // WRONG — moves away from base case
}

// badCountdown(5); // Stack overflow!

---

5. Classic examples

Factorial

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

console.log(factorial(0));  // 1
console.log(factorial(1));  // 1
console.log(factorial(5));  // 120
console.log(factorial(10)); // 3628800

Fibonacci

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Each number is the sum of the two before it: fib(n) = fib(n-1) + fib(n-2).

function fibonacci(n) {
  if (n <= 0) return 0;  // Base case 1
  if (n === 1) return 1; // Base case 2
  return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}

console.log(fibonacci(0));  // 0
console.log(fibonacci(1));  // 1
console.log(fibonacci(6));  // 8
console.log(fibonacci(10)); // 55

Warning: This naive recursive Fibonacci is extremely slow for large n because it recalculates the same values many times (O(2^n)). See the optimized version in Section 8.

Countdown

function countdown(n) {
  if (n <= 0) {
    console.log("Liftoff!");
    return;
  }
  console.log(n);
  countdown(n - 1);
}

countdown(3);
// 3
// 2
// 1
// Liftoff!

Sum of an array

function sumArray(arr) {
  if (arr.length === 0) return 0; // Base case: empty array
  return arr[0] + sumArray(arr.slice(1)); // First element + sum of the rest
}

console.log(sumArray([1, 2, 3, 4, 5])); // 15

Exponentiation

function power(base, exp) {
  if (exp === 0) return 1;           // Base case
  return base * power(base, exp - 1); // Recursive case
}

console.log(power(2, 10)); // 1024
console.log(power(3, 4));  // 81

---

6. Recursive vs iterative — when to prefer which

Aspect	Recursive	Iterative (loop)
Readability	Often cleaner for tree/graph problems	Clearer for linear sequences
Performance	Call stack overhead per frame	Generally faster (no stack frames)
Stack risk	Can overflow for deep recursion	No stack overflow risk
State	Managed implicitly via parameters	Managed explicitly with variables
Best for	Trees, nested structures, divide-and-conquer	Counting, accumulation, flat iteration

Side-by-side: Factorial

// Recursive
function factorialRecursive(n) {
  if (n <= 1) return 1;
  return n * factorialRecursive(n - 1);
}

// Iterative
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

// Both produce the same results
console.log(factorialRecursive(10)); // 3628800
console.log(factorialIterative(10)); // 3628800

Side-by-side: Fibonacci

// Recursive (slow — O(2^n))
function fibRecursive(n) {
  if (n <= 0) return 0;
  if (n === 1) return 1;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// Iterative (fast — O(n))
function fibIterative(n) {
  if (n <= 0) return 0;
  if (n === 1) return 1;

  let prev = 0;
  let curr = 1;
  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  return curr;
}

console.log(fibIterative(50)); // 12586269025 — instant
// fibRecursive(50) would take a VERY long time

Rule of thumb: Use recursion when the data structure is naturally recursive (trees, nested objects). Use iteration for flat sequences where performance matters.

---

7. Recursive data structures

Recursion truly shines when working with nested or tree-like data.

Traversing a nested object

function findValue(obj, targetKey) {
  for (const key in obj) {
    if (key === targetKey) return obj[key];

    if (typeof obj[key] === "object" && obj[key] !== null) {
      const result = findValue(obj[key], targetKey); // Recurse into nested object
      if (result !== undefined) return result;
    }
  }
  return undefined;
}

const config = {
  app: {
    name: "MyApp",
    settings: {
      theme: "dark",
      language: "en",
    },
  },
};

console.log(findValue(config, "theme"));    // "dark"
console.log(findValue(config, "language")); // "en"
console.log(findValue(config, "missing"));  // undefined

Flatten a nested array

function flatten(arr) {
  const result = [];

  for (const item of arr) {
    if (Array.isArray(item)) {
      result.push(...flatten(item)); // Recurse on nested arrays
    } else {
      result.push(item);
    }
  }

  return result;
}

console.log(flatten([1, [2, 3], [4, [5, [6]]]]));
// [1, 2, 3, 4, 5, 6]

console.log(flatten([1, 2, 3]));
// [1, 2, 3] — no nesting, works fine

Deep clone an object

function deepClone(value) {
  // Base cases: primitives and null
  if (value === null || typeof value !== "object") {
    return value;
  }

  // Handle arrays
  if (Array.isArray(value)) {
    return value.map(item => deepClone(item));
  }

  // Handle objects
  const clone = {};
  for (const key in value) {
    if (value.hasOwnProperty(key)) {
      clone[key] = deepClone(value[key]); // Recurse on each property
    }
  }
  return clone;
}

const original = {
  name: "Alice",
  scores: [90, 85, 92],
  address: { city: "NYC", zip: "10001" },
};

const copy = deepClone(original);
copy.scores.push(100);
copy.address.city = "LA";

console.log(original.scores);       // [90, 85, 92] — unchanged
console.log(original.address.city); // "NYC" — unchanged
console.log(copy.scores);           // [90, 85, 92, 100]
console.log(copy.address.city);     // "LA"

Directory traversal concept

// Conceptual — simulated file tree
const fileTree = {
  name: "root",
  type: "folder",
  children: [
    { name: "index.html", type: "file" },
    {
      name: "src",
      type: "folder",
      children: [
        { name: "app.js", type: "file" },
        { name: "utils.js", type: "file" },
        {
          name: "components",
          type: "folder",
          children: [
            { name: "Header.js", type: "file" },
            { name: "Footer.js", type: "file" },
          ],
        },
      ],
    },
  ],
};

function listAllFiles(node, path = "") {
  const currentPath = path ? `${path}/${node.name}` : node.name;

  if (node.type === "file") {
    console.log(currentPath);
    return;
  }

  // Folder — recurse into children
  if (node.children) {
    for (const child of node.children) {
      listAllFiles(child, currentPath);
    }
  }
}

listAllFiles(fileTree);
// root/index.html
// root/src/app.js
// root/src/utils.js
// root/src/components/Header.js
// root/src/components/Footer.js

---

8. Tail call optimization (TCO)

Tail call optimization is when the engine reuses the current stack frame for a recursive call that is the last operation in the function (a "tail call"). This prevents stack overflow for deep recursion.

What is a tail call?

A tail call is when the recursive call is the very last thing the function does — no further computation after it returns:

// NOT a tail call — multiplication happens AFTER the recursive call returns
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // Must wait for factorial(n-1), then multiply
}

// TAIL CALL — the recursive call IS the return value (no extra work after)
function factorialTail(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, n * accumulator); // Tail position
}

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

Why TCO matters

With TCO, factorialTail(100000) would work without stack overflow because the engine reuses the same frame. Without TCO, it overflows.

Browser support reality

TCO is part of the ES6 spec but as of now, only Safari implements it. V8 (Chrome, Node.js) and SpiderMonkey (Firefox) have not implemented it. This means:

• Write tail-recursive code for clarity when it makes sense.
• Do not rely on TCO for correctness — convert to iteration if stack depth is a concern.
• Use trampolining as a workaround (advanced technique):

// Trampoline — manually manages the stack
function trampoline(fn) {
  return function (...args) {
    let result = fn(...args);
    while (typeof result === "function") {
      result = result();
    }
    return result;
  };
}

function factorialTrampoline(n, acc = 1) {
  if (n <= 1) return acc;
  return () => factorialTrampoline(n - 1, n * acc); // Returns a function, not a call
}

const factorial = trampoline(factorialTrampoline);
console.log(factorial(5));      // 120
console.log(factorial(100000)); // Infinity (number overflow, but no stack overflow!)

---

9. Real examples

Fibonacci with memoization (fixing the performance problem)

function fibonacciMemo(n, memo = {}) {
  if (n in memo) return memo[n]; // Return cached result
  if (n <= 0) return 0;
  if (n === 1) return 1;

  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

console.log(fibonacciMemo(10));  // 55
console.log(fibonacciMemo(50));  // 12586269025 — instant!
console.log(fibonacciMemo(100)); // 354224848179261915075n... (safe with BigInt for exact)

Recursive search in a DOM-like tree

function findElementById(node, id) {
  if (node.id === id) return node;

  if (node.children) {
    for (const child of node.children) {
      const found = findElementById(child, id);
      if (found) return found;
    }
  }

  return null;
}

// Simulated DOM-like tree
const dom = {
  tag: "div", id: "root", children: [
    { tag: "header", id: "header", children: [
      { tag: "nav", id: "nav", children: [] },
    ]},
    { tag: "main", id: "main", children: [
      { tag: "article", id: "post-1", children: [] },
      { tag: "article", id: "post-2", children: [] },
    ]},
  ],
};

console.log(findElementById(dom, "post-2")); // { tag: "article", id: "post-2", ... }
console.log(findElementById(dom, "missing")); // null

Sum of all numbers in a nested structure

function deepSum(value) {
  if (typeof value === "number") return value;
  if (Array.isArray(value)) {
    return value.reduce((sum, item) => sum + deepSum(item), 0);
  }
  if (typeof value === "object" && value !== null) {
    return Object.values(value).reduce((sum, v) => sum + deepSum(v), 0);
  }
  return 0; // strings, booleans, etc.
}

const data = {
  a: 1,
  b: [2, 3, [4, 5]],
  c: { d: 6, e: { f: 7 } },
};

console.log(deepSum(data)); // 28 (1+2+3+4+5+6+7)

---

10. Common mistakes

Mistake	What happens	Fix
No base case	Infinite recursion, stack overflow	Always define when to stop
Base case never reached	Same as above	Ensure each recursive call moves toward the base case
Mutating shared state	Unexpected results across recursive calls	Use parameters or create new objects
Forgetting to return	Returns undefined instead of the recursive result	Always return the recursive call
Off-by-one in base case	Wrong result or one extra call	Trace through small inputs manually

// BUG: Forgot to return the recursive call
function sumBad(n) {
  if (n <= 0) return 0;
  sumBad(n - 1); // Missing return!
}

console.log(sumBad(5)); // undefined

// FIX:
function sumGood(n) {
  if (n <= 0) return 0;
  return n + sumGood(n - 1); // Return the result
}

console.log(sumGood(5)); // 15

---

Key takeaways

1. Recursion = a function calling itself. Every recursive function needs a base case (stop) and a recursive case (call itself with smaller input).
2. The call stack holds one frame per active function call — deep recursion means many frames, risking stack overflow.
3. Classic problems (factorial, fibonacci, countdown) demonstrate the pattern clearly.
4. Recursive solutions excel at tree and nested structure problems (DOM traversal, deep clone, flatten).
5. Iterative solutions are usually faster and stack-safe — prefer them for simple linear problems.
6. Memoization fixes the exponential cost of naive recursive Fibonacci by caching results.
7. Tail call optimization (TCO) is in the spec but only Safari supports it — do not rely on it; use trampolines or convert to loops.
8. Always trace through small inputs by hand to verify your base case and recursive case work correctly.

---

Explain-It Challenge

Explain without notes:

1. What are the two required parts of every recursive function?
2. What causes a stack overflow and how do you prevent it?
3. Why is the naive recursive Fibonacci so slow? How does memoization fix it?
4. Give one example where recursion is clearly better than a loop.

---

Navigation: ← 1.20.f — Practice Problems · 1.20 Overview