Learn JS Series (#24) - Recursion: Base Cases, the Call Stack, and Stack Overflows

What will I learn

You will learn what recursion is, and the two ingredients every recursive function needs;
how the call stack drives function calls, and how recursion builds up on it;
what a stack overflow is, and the input sizes that cause one;
how to recurse over nested data structures like trees, where recursion truly shines;
when recursion is the right tool and when a plain loop is better.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Node.js (20+) distribution, or just a modern browser console;
Episodes 1-23 read, especially functions and scope.

Difficulty

Intermediate

Curriculum (of the `Learn JS Series`):

Learn JS Series (#24) - Recursion: Base Cases, the Call Stack, and Stack Overflows

Solutions to Episode 23 Exercises

Exercise 1 - call and apply:

function sayCity() { return this.city; }
console.log(sayCity.call({ city: "amsterdam" }));  // "amsterdam"
console.log(sayCity.apply({ city: "berlin" }));    // "berlin"

The insight: with no arguments to pass, call and apply look identical; the difference only appears when you pass arguments (list versus array).

Exercise 2 - partial application with bind:

function multiply(a, b, c) { return a * b * c; }
const times12 = multiply.bind(null, 3, 4); // a=3, b=4 fixed
console.log(times12(2)); // 24

The insight: null is passed as this because multiply does not use it; the following arguments pre-fill a and b.

Exercise 3 - a bound logger:

const logger = {
  prefix: "[LOG]",
  write(msg) { return `${this.prefix} ${msg}`; },
};
const boundWrite = logger.write.bind(logger);
setTimeout(() => console.log(boundWrite("started")), 10); // "[LOG] started"

The insight: binding locks this to logger, so the detached function keeps the right prefix; unbound, this would be undefined.

With this finally nailed down over the last two episodes, we change gears completely. Today is about a single idea that trips up almost every beginner and then, once it clicks, becomes one of the most satisfying tools you own: functions that call themselves. Recursion.

What recursion is

Recursion is when a function calls itself to solve a problem by breaking it into smaller versions of the same problem. It sounds circular, and it would be an infinite loop, except for one crucial ingredient: every recursive function needs a base case, a condition where it stops calling itself and just returns an answer. Without a base case, it recurses forever (until it crashes, which we will see happen shortly).

So every recursive function has two parts, and I want you to memorize this template because it never changes:

The base case: the simplest input, where the answer is known directly, no more recursion.
The recursive case: reduce the problem toward the base case, and call yourself on the smaller piece.

The classic first example is factorial (n! = n times (n-1) times ... times 1). Read the two comments and you will see the template staring right back at you:

function factorial(n) {
  if (n <= 1) return 1;          // base case: 0! and 1! are 1
  return n * factorial(n - 1);   // recursive case: n * (n-1)!
}
console.log(factorial(5)); // 120  (5 * 4 * 3 * 2 * 1)

Trace it slowly, because this trace is the whole mental model. factorial(5) cannot return yet -- it needs the value of factorial(4) first. So it pauses, half-finished, and asks for factorial(4), which in turn pauses and asks for factorial(3), and so on down to factorial(1), which hits the base case and returns 1 immediately. NOW the paused calls can finish, in reverse order: factorial(2) becomes 2 * 1 = 2, then factorial(3) becomes 3 * 2 = 6, then 4 * 6 = 24, then 5 * 24 = 120. The descent goes down to the base case, and the answer bubbles back up. That down-then-up shape is recursion in a nutshell.

A second linear example makes the template even clearer -- summing an array by walking an index toward its end:

function sumList(arr, i = 0) {
  if (i === arr.length) return 0;      // base case: past the end, nothing left to add
  return arr[i] + sumList(arr, i + 1); // recursive case: this element + the sum of the rest
}
console.log(sumList([10, 20, 30])); // 60

Every recursive function you will ever write is a variation on those two you just read: check for the base case first, otherwise do a little work and hand the smaller remainder to yourself. If you find your recursion misbehaving, nine times out of ten the base case is wrong, missing, or unreachable. Check it FIRST.

The call stack

To really understand recursion, you must understand the call stack, the mechanism JavaScript uses to keep track of function calls (we go a lot deeper on it in Phase 7, but you need the essentials now). Every time you call a function, JavaScript pushes a "frame" onto the stack. That frame holds the call's local variables, its arguments, and a note of where to return to when the function finishes. When the function returns, its frame is popped off the top. The stack is strictly last-in-first-out, like a stack of plates -- you can only add to or take from the top.

Here is the connection to recursion: with a recursive function, each self-call adds another frame before the previous one has finished. The outer call is still sitting there, paused, waiting for its result. So the stack grows deeper and deeper as you descend, and only unwinds once the base case is reached:

function countdown(n) {
  if (n === 0) {
    console.log("liftoff");
    return;
  }
  console.log(n);
  countdown(n - 1); // a new frame stacks on top before this call returns
}
countdown(3); // 3, 2, 1, liftoff

Picture the stack at the deepest point of countdown(3). There are four frames piled up: countdown(3) at the bottom, then countdown(2), then countdown(1), then countdown(0) on top. All four exist AT THE SAME TIME, each holding its own n. Only when countdown(0) prints "liftoff" and returns do the frames pop off one by one, from the top down, until the stack is empty again. That growing-then-shrinking pile is exactly what you must picture to reason about ANY recursion, no matter how fancy. When people say recursion "feels like magic", it is almost always because they have not yet pictured the stack. Once you do, the magic turns into plain mechanics.

Stack overflows

Now, that stack is not infinite. It is a finite region of memory, and every recursive call consumes one frame of it. So recursion that goes too deep -- or that forgets its base case entirely -- runs out of stack space and crashes with a stack overflow. In JavaScript the error reads Maximum call stack size exceeded (technically a RangeError):

function forever(n) {
  return forever(n + 1); // no base case! recurses until the stack is full
}
// forever(0); // ERROR (runtime): Maximum call stack size exceeded

That one is an obvious bug -- no base case, so it can only ever crash. But here is the part that surprises people: even a perfectly correct recursion can overflow, purely because the depth is too large. Our sumList from earlier is completely correct, yet feed it a huge array and it will blow the stack, because it stacks one frame per element:

function sumTo(n) {
  if (n === 0) return 0;
  return n + sumTo(n - 1); // one frame per number - fine for small n
}
console.log(sumTo(1000));    // 500500 - works comfortably
// console.log(sumTo(100000)); // ERROR (runtime): Maximum call stack size exceeded

sumTo(1000) is fine, but sumTo(100000) tries to stack a hundred thousand frames and dies. A plain loop doing the same arithmetic would not even blink, because a loop reuses ONE frame no matter how many times it iterates. JavaScript engines typically allow only somewhere around ten-to-fifteen thousand nested frames (the exact number depends on the engine and how much each frame holds), so deep linear recursion is a real, practical constraint you must respect. This is precisely why, for simple linear repetition over large counts, a loop is the safer choice -- it cannot overflow.

Where recursion shines: nested structures

If loops are safer for simple counting, why use recursion at all? Fair question. The answer is that some data is naturally recursive, and for that data, recursion is dramatically clearer than any loop. Trees, nested objects, folder structures on your disk, the DOM in a web page -- these are all recursive by nature: a node contains nodes that contain nodes, to an unknown depth. Recursion mirrors that shape perfectly, because a recursive function is literally "a thing that contains a smaller version of itself", which is the same sentence that describes the data.

Consider summing all the numbers in an arbitrarily nested array. This is genuinely painful with plain loops (you would need your own explicit stack), but it is elegant with recursion:

function deepSum(arr) {
  let total = 0;
  for (const item of arr) {
    if (Array.isArray(item)) {
      total += deepSum(item); // recurse into nested arrays
    } else {
      total += item;          // base case: a plain number, just add it
    }
  }
  return total;
}
console.log(deepSum([1, [2, 3, [4, 5]], 6])); // 21

The beautiful thing is that deepSum does not need to know, and does not care, how deep the nesting goes. Each level handles its own plain numbers and delegates any nested arrays to another call, which does exactly the same at its level. The structure could be three deep or thirty deep -- the code is identical. Walking a nested object is the very same idea, just reading values instead of array elements:

function countKeys(obj) {
  let count = 0;
  for (const value of Object.values(obj)) {
    count += 1;
    if (value && typeof value === "object") {
      count += countKeys(value); // recurse into nested objects
    }
  }
  return count;
}
console.log(countKeys({ a: 1, b: { c: 2, d: { e: 3 } } })); // 5

And once you see the pattern, real tree structures fall out naturally. Here is a little tree of nodes, each with a value and a list of children, summed with a handful of lines:

const tree = {
  value: 1,
  children: [
    { value: 2, children: [] },
    { value: 3, children: [{ value: 4, children: [] }] },
  ],
};
function sumTree(node) {
  let total = node.value;               // count this node
  for (const child of node.children) {  // then delegate each subtree to a recursive call
    total += sumTree(child);
  }
  return total;
}
console.log(sumTree(tree)); // 10  (1 + 2 + 3 + 4)

Notice something important that separates these from countdown: this data BRANCHES. A node can have several children, so a single call can spawn several recursive calls, not just one. That branching is exactly where recursion stops being a mere alternative to a loop and becomes the natural, and often the only sane, way to express the problem. Try writing sumTree with plain loops and you will very quickly reinvent a stack of your own -- at which point you have written recursion the hard way. ;-)

Recursion versus iteration

So how do you actually choose between a loop and a recursion in practice? Here is a guideline I have leaned on for years. For simple, linear repetition -- count to n, sum a flat array, walk a list once -- prefer a loop. It is efficient, it is easy to read, and crucially it cannot overflow. For inherently nested or branching structures -- trees, nested data, folder trees, and divide-and-conquer algorithms like quicksort or binary search -- prefer recursion, because it matches the shape of the problem and keeps the code honest.

This next one is the poster child for "just use a loop". It is linear, the count can be enormous, and a loop handles it without breaking a sweat where recursion would overflow:

// linear task with a potentially huge count: a loop is the better fit
function sumTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}
console.log(sumTo(1000000)); // 500000500000 - fine as a loop; recursion would overflow

It is worth knowing that ANY recursion can, in principle, be rewritten as a loop with an explicit stack that you manage by hand. Sometimes that is the right move (when depth is unbounded and could overflow). But it is often uglier and harder to follow, so the honest rule is: use recursion when it makes the code CLEARER and the depth is safely bounded; reach for a loop (or a manual stack) when the depth could be huge. The mental checklist is short. Is the data or algorithm naturally nested or branching? Recurse. Is it flat and linear, possibly with huge counts? Loop. Get that instinct right and recursion becomes a precise instrument in stead of a party trick.

How other languages handle this

Since quit a few of you arrived here from the Learn Python Series, with some Rust and Go readers mixed in, a look sideways is genuinely illuminating -- because the "deep recursion overflows the stack" story plays out very differently across languages, and it is not just trivia.

Python is actually STRICTER than JavaScript here. It ships a deliberate recursion limit (1000 by default) and raises a clean RecursionError long before the real machine stack is exhausted, as a safety guard. You can raise the ceiling with sys.setrecursionlimit, but the deeper lesson is the same as in JS: Python has no tail-call optimization either, so deep linear recursion is discouraged, and Pythonistas reach for a loop:

import sys

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(900))          # fine, under the default limit
# print(sum_to(100000))     # RecursionError: maximum recursion depth exceeded
sys.setrecursionlimit(200000)  # you CAN raise it, but a loop is wiser

Rust has no this and no runtime recursion guard -- it simply recurses on the real stack, and if you go too deep the program aborts with a stack overflow, exactly like JavaScript, just less politely. Rust does not guarantee tail-call optimization either, so idiomatic Rust for a linear job is a plain loop, which never touches stack depth at all:

fn sum_to(n: u64) -> u64 {
    let mut total = 0;
    for i in 1..=n {
        total += i;      // a loop: constant stack usage, no overflow ever
    }
    total
}

fn main() {
    println!("{}", sum_to(1_000_000)); // 500000500000
}

Go is the interesting outlier. Goroutines start with a tiny stack (a few kilobytes) that GROWS automatically as needed, up to a large limit (a gigabyte by default on 64-bit systems). So Go tolerates FAR deeper recursion than JavaScript or Python before it ever complains -- the stack quietly resizes under you:

package main

import "fmt"

func sumTo(n int) int {
    if n == 0 {
        return 0
    }
    return n + sumTo(n-1) // Go's growable stack handles very deep recursion
}

func main() {
    fmt.Println(sumTo(1000000)) // works - the goroutine stack grew to fit
}

So the same recursive function overflows quickly in JS and Python, less quickly (but still) in Rust, and survives enormous depths in Go. The takeaway is not "Go is best" -- it is that stack depth is an implementation reality of your runtime, not a property of recursion itself. As an aside for the curious: the JavaScript spec actually DID add proper tail calls in ES2015, which would let certain recursions run in constant stack space, but in practice only Safari's engine ever shipped it -- V8 (so Node and Chrome) never did. That is why, in the JavaScript you will actually run, deep linear recursion overflows and a loop is the pragmatic answer. Having said that, for nested and branching data, recursion remains the clear winner in every one of these languages. ;-)

Try it yourself

Three exercises, increasing in difficulty. Write the base case FIRST every time, then the recursive case -- and predict the output before you run it. Full solutions open the next episode.

Write a recursive power(base, exponent) that computes base to the exponent (assume a non-negative integer exponent). Identify your base case explicitly in a comment. Test power(2, 10).
Write a recursive function flatten(arr) that turns an arbitrarily nested array of numbers into a flat array, so flatten([1, [2, [3, 4]], 5]) returns [1, 2, 3, 4, 5]. (Hint: check Array.isArray and concatenate results.)
Deliberately write a recursion with no base case and describe (do not necessarily run it to a crash) what error you would get and why. Then add a base case that stops it, and explain in words how the call stack grows and then shrinks for a small input like 3.

So what did we actually cover?

Recursion is a function calling itself; every recursive function needs a base case (where it stops) and a recursive case (reducing the problem toward the base).
The call stack tracks calls with frames; recursion stacks a new frame per self-call, growing deep on the way down and unwinding on the way back up.
Too much depth (or a missing base case) causes a stack overflow, since the stack is finite (~10k-15k frames in typical JS engines).
Recursion shines on naturally nested and branching data -- trees, nested arrays, nested objects -- where it mirrors the structure clearly and does not care how deep it goes.
Choose a loop for simple linear repetition (safe, no overflow) and recursion for nested or divide-and-conquer problems; stack behaviour differs across JS, Python, Rust, and Go.

Next episode we look at IIFEs and the module pattern, the clever pre-2015 technique that used functions and closures to create privacy and organize code before JavaScript had real modules.

See you in the next episode, happy recursing.

@scipio

Learn JS Series (#24) - Recursion: Base Cases, the Call Stack, and Stack Overflows

Learn JS Series (#24) - Recursion: Base Cases, the Call Stack, and Stack Overflows

What will I learn

Requirements

Difficulty

Curriculum (of the Learn JS Series):

Learn JS Series (#24) - Recursion: Base Cases, the Call Stack, and Stack Overflows

Solutions to Episode 23 Exercises

What recursion is

The call stack

Stack overflows

Where recursion shines: nested structures

Recursion versus iteration

How other languages handle this

Try it yourself

So what did we actually cover?

See you in the next episode, happy recursing.

Curriculum (of the `Learn JS Series`):