Skip to main content
πŸ” Recursion

Trace the Call Stack

A recursive function is one that calls itself. That sounds dizzying, so before you write one, let's slow down and watch one run.

Here's a tiny countdown. Read it top to bottom:

function countdown(n) {
  if (n <= 0) return [];            // base case: stop here
  return [n, ...countdown(n - 1)];  // recursive step: n, then count down the rest
}

Now let's trace countdown(3) by hand. Each call pauses and waits for the call inside it to finish β€” the paused calls stack up:

countdown(3) β†’ [3, ...countdown(2)]   ⏸ waiting on countdown(2)
  countdown(2) β†’ [2, ...countdown(1)]   ⏸ waiting on countdown(1)
    countdown(1) β†’ [1, ...countdown(0)]   ⏸ waiting on countdown(0)
      countdown(0) β†’ []   βœ… base case! nothing to wait for

The bottom call hits the base case and returns []. Now the stack unwinds β€” each paused call fills in its blank and returns:

countdown(0) returns []
countdown(1) returns [1, ...[]]      β†’ [1]
countdown(2) returns [2, ...[1]]     β†’ [2, 1]
countdown(3) returns [3, ...[2, 1]]  β†’ [3, 2, 1]

Two ideas to hold onto: a recursive call goes down until it hits the base case, then comes back up building the answer. Trace it in your head, then answer below. πŸ‘‡

What stops countdown from calling itself forever?

In the trace, which call returns FIRST (reaches its answer before any other)?

While countdown(3) is waiting, how many calls are paused on the stack at the deepest point?

What does countdown(3) ultimately return?