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. π