DAY 9 / 30 · WEEK 2

Recursion & the Call Stack

Goal of the day

• Write a recursive function with a correct base case and recursive case.
• Visualize the call stack growing (calls) and shrinking (returns) as recursion runs.
• Know why deep recursion can crash — and when to prefer an iterative version instead.

Concept

Recursion is like asking a question to someone who doesn't know the answer, so they ask someone else the same question but for a smaller version of the problem — and so on, until someone (the base case) knows the answer directly without asking anyone else. Then everyone reports their answer back up the chain, each person using the answer they received to compute their own.

Under the hood, JavaScript tracks this chain with an actual data structure: the call stack. Every function call pushes a new frame onto the stack — remembering where to resume once that call returns. Every return pops the top frame off and hands its value back to whoever called it. A recursive function without a correct base case never stops pushing — and since the stack has a fixed size limit, that crashes with a RangeError: Maximum call stack size exceeded.

Diagram

Interactive visualizations

1. factorial(5) — linear recursion

2. Reverse a string recursively

The code

// Every recursive function needs exactly these two parts:

function factorial(n) {
  if (n <= 1) return 1;              // BASE CASE — stops the recursion
  return n * factorial(n - 1);       // RECURSIVE CASE — smaller sub-problem
}

function reverseStr(s) {
  if (s === '') return '';           // BASE CASE — empty string reverses to itself
  return reverseStr(s.slice(1)) + s[0]; // RECURSIVE CASE — reverse the rest, append first char
}

Line by line:

• factorial's base case triggers at n <= 1 (not just n === 0) — this guards against ever calling factorial(-1) if someone passes a negative number by mistake, which would recurse forever.
• reverseStr's recursive case calls itself with a strictly smaller input (s.slice(1) is always one character shorter) — every recursive function must shrink the problem toward the base case, or it never terminates.
• Notice the recursive call happens before the work that uses its result (n * and + s[0]) — that's what forces the stack to grow all the way down to the base case before any multiplication or concatenation actually happens.

Dry run: factorial(4)

Complexity

Same time complexity, very different space — this is the classic recursion trade-off: recursive code often reads more clearly, but it costs O(depth) stack space that an equivalent loop wouldn't need.

Interview corner

• What are the two required parts of every recursive function? A base case that returns without recursing, and a recursive case that calls itself with a strictly smaller input. Missing either one causes infinite recursion.
  ⚠ Trap: a base case that exists but is unreachable (e.g. checking n === 0 when the input can skip past zero, like counting down by 2 from an odd number) is just as broken as having no base case at all.
• Why does deep recursion crash in JavaScript? Each call frame uses real memory on a stack of limited size (typically low thousands of frames, engine-dependent). Recurse deeper than that and you get RangeError: Maximum call stack size exceeded.
  ↳ Common follow-up: "Doesn't tail call optimization fix this?" — in the language spec, yes, but almost no JS engine (including V8, which powers Chrome and Node) actually implements it in practice. Don't rely on TCO in JavaScript.
• When would you rewrite a recursive solution as iterative? When the input could be large enough to risk a stack overflow, or when the recursive version's O(depth) space cost genuinely matters — e.g. processing a very long linked list or a deep tree recursively vs. with an explicit stack/loop.

How to talk through it out loud: state the base case and recursive case explicitly before writing code — "the base case is an empty string, which reverses to itself; the recursive case reverses everything after the first character, then appends it." Interviewers are listening for that structure, not just working code.

Practice problems

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
// Note: this naive version is O(2^n) — very slow for large n.
// We fix that with memoization on Day 25.

function isPowerOfTwo(n) {
  if (n <= 0) return false;
  if (n === 1) return true;
  if (n % 2 !== 0) return false;
  return isPowerOfTwo(n / 2);
}

function myPow(x, n) {
  if (n < 0) return 1 / myPow(x, -n);
  if (n === 0) return 1;
  const half = myPow(x, Math.floor(n / 2));
  return n % 2 === 0 ? half * half : half * half * x;
}

Quiz