Day 9: Recursion & the Call Stack

DAY 9 / 30 · WEEK 2

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

Calling factorial(3) pushes three frames onto the stack, newest call on top. factorial(1) is the base case — it returns 1 directly, no further calls. Once it returns, the stack shrinks: factorial(1) pops off, factorial(2) resumes and multiplies by the 1 it got back (2 × 1 = 2), then pops itself, and factorial(3) resumes the same way.

currently executing returning this step waiting on the stack

1. factorial(5) — linear recursion

Press Play or Step to begin.

call stack depth: 0

Step 0 / 0

▶ PlayStep ⏭⟲ Reset🔀 Shuffle

2. Reverse a string recursively — reverseStr("abcd")

Press Play or Step to begin.

call stack depth: 0

Step 0 / 0

▶ PlayStep ⏭⟲ Reset🔀 Shuffle

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)

Call	Action	Waiting on
factorial(4)	4 > 1, call factorial(3)	factorial(3)’s result
factorial(3)	3 > 1, call factorial(2)	factorial(2)’s result
factorial(2)	2 > 1, call factorial(1)	factorial(1)’s result
factorial(1)	1 <= 1 — base case, return 1	—
factorial(2) resumes	2 × 1 = 2, return 2	—
factorial(3) resumes	3 × 2 = 6, return 6	—
factorial(4) resumes	4 × 6 = 24, return 24	—

Complexity

Approach	Time	Space	Why
Recursive factorial(n)	O(n)	O(n)	n calls deep — every waiting frame sits on the call stack until it returns.
Iterative factorial(n)	O(n)	O(1)	A single loop variable, no call stack growth at all.

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

1. Fibonacci Number — Easy

LeetCode: Fibonacci Number

Given n, return the nth Fibonacci number (F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)).

Hint

Two base cases this time (n=0 and n=1), not just one — write both before the recursive case.

Show solution

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.

2. Power of Two — Easy

LeetCode: Power of Two

Given an integer, return true if it’s a power of two.

Hint

Think about what’s special about the binary representation of a power of two. What would recursively shrinking n toward 1 look like, and what should stop it early?

Show solution

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

3. Pow(x, n) — Medium

LeetCode: Pow(x, n)

Implement x^n (x to the power n), where n can be negative.

Hint

Multiplying x by itself n times is O(n) — today’s Pow(x,n) is about beating that. What operation from earlier this week cuts a problem in half every step instead of shrinking by one?

Show solution

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

Quiz: 1. Every correct recursive function needs:

A base case AND a recursive case that shrinks the problem

A base case that stops the recursion and a recursive case that shrinks toward it are both required — missing either causes infinite recursion.

Quiz: 2. Each recursive call does what to the call stack?

Pushes a new frame

Every function call — recursive or not — pushes a new frame onto the call stack, which is popped when that call returns.

Quiz: 3. What happens when recursion goes too deep in JavaScript?

RangeError: Maximum call stack size exceeded

Too many stacked frames without returning hits the engine’s call stack size limit and throws a RangeError.

Quiz: 4. What’s the space complexity of the recursive factorial(n), and why?

O(n) — n frames stack up before any of them return

Recursive factorial(n) makes n nested calls, each sitting on the stack until it returns — O(n) extra space, unlike the O(1) space of a loop.

Quiz: 5. Which of these is just as broken as having no base case at all?

A base case that technically exists but is unreachable for some inputs

A base case that technically exists but can never actually be hit (e.g. checking n===0 when n can skip past zero) is functionally the same bug as having no base case at all.