The call stack, and what "stack overflow" means

The stack is a place, not a list

A list grows as long as you need. The stack does not. It is a region of memory with a first address and a last one, handed to your program when it starts, and every frame is carved out of that fixed space. This is why the animation draws the empty rows: the room that is left is as much a part of the picture as the frames that are using it.

Notice the direction. The first frame sits at the highest address and each new one is placed below it. That is not a drawing choice. On x86-64, Arm and every other mainstream architecture, the stack grows downwards from a high address towards lower ones, which is why the limit in the animation is at the bottom rather than the top.

Where the bytes go

Each frame in this lesson takes 64 bytes, which is a realistic figure for a function this small: room for the address to return to, the caller's frame pointer, a local or two, and the padding the machine insists on for alignment. Change n and watch the usage figure underneath. It is always the number of frames multiplied by the size of one, because nothing else is in there.

That is the cost recursion has and a loop does not. Depth is memory. Ten calls deep is ten frames alive at once, and all ten are still holding their values, because not one of them has finished.

Running out

runaway is sum with the stopping condition deleted. It is not an exotic mistake. It is the single most common way a recursive function goes wrong, and it comes in two flavours: forgetting the base case, and writing one that the input never reaches.

Watch what happens at the bottom. The call asks for a frame, there is nowhere to put it, and the program stops there. It does not overwrite something else and carry on. It does not free an old frame to make room, because every one of those frames is still waiting for an answer. Nothing can be thrown away, and nothing more can be added, so there is nothing left to do.

That is a stack overflow. The name is literal: the thing that overflowed is the stack, and it overflowed because it was a container all along.

The fix is usually a loop

Switch to loop and set n as high as it will go. One frame. The same frame, reused, for every value from n down to one. Iteration keeps its working values in the frame it already has, so its memory cost does not change with the size of the problem.

That is the trade, stated plainly: recursion buys code that matches the shape of the problem, and pays for it in frames. When the depth is small, or bounded by the structure you are walking, the price is nothing. When the depth grows with the input, the price is the whole stack.

The real numbers

The ceiling in the animation is 10 frames, and that is a lie of convenience. It has to be small enough to draw and slow enough to watch. A real thread is given far more: on 64-bit Linux the main thread usually gets 8 MB, threads you create yourself typically get 1 MB, and the main thread on macOS gets 8 MB while its secondary threads get 512 KB.

Do the division and the numbers stop being abstract. At 64 bytes a frame, 8 MB is room for about 131,000 calls; 1 MB is about 16,000; 512 KB is about 8,000. So a recursive function that goes a few thousand deep is fine on a main thread and can die on a worker thread, using exactly the same code. Depth limits are a property of the thread, not of the language.

JavaScript engines add their own limit below the operating system's. V8 stops at roughly 10,000 to 12,000 frames for a small function and throws a RangeError rather than letting the process die, which is why a runaway recursion in a browser gives you a stack trace instead of taking the tab down. The exact number moves with the frame size, so a function with more locals runs out sooner. It is not a fixed count of calls, however often it is quoted as one.

Why the frame is that size

A frame is not just your variables. Calling a function on x86-64 pushes the return address, saves the caller's frame pointer, and leaves room for the locals that could not be kept in registers and for any registers the callee must preserve. The System V ABI also requires the stack pointer to be 16-byte aligned at a call, so a frame that needs 40 bytes of content will occupy 48.

This is also why the simple advice “just use fewer variables” helps less than people expect. You can shrink a frame, but you cannot shrink it below the fixed cost of making a call, so you change the constant and not the shape.

Tail calls, and why they rarely save you

A call in tail position is the last thing a function does, with no work waiting for its result. Such a call does not need its caller's frame kept alive, so a compiler is free to reuse it, which turns the recursion into a loop and the memory cost into a constant.

Scheme requires this. Several functional languages do it. JavaScript engines, with one historical exception, do not, despite it being in the specification. So in the vehicle language of this lesson, rewriting sum into tail position does not change what you see in the animation. Worth knowing, but it is not the answer to a depth problem in most of the languages people actually meet.

When you cannot use a loop

Sometimes the recursion is not a convenience, because you do not know the depth in advance: walking a directory tree, parsing nested structures, following links from page to page. The standard answer there is to keep the algorithm and move the stack. You declare your own stack as an ordinary array, push what the recursive version would have called with, and loop until it is empty.

That does not remove the memory cost. It moves it from the stack, which is small and fixed, to the heap, which is large and can grow. The picture stays the same shape. Only the region it is drawn in changes, and that is usually enough.

One more detail worth having: runaway reaches the ceiling in 13 recorded steps at the size drawn here, and it would reach a real one just as certainly, only later. Depth that grows without a stopping condition does not have a safe size.

Problems

Work them before opening the answers. Reading a solution feels like learning and is not.

function countdown(n) {
  console.log(n)
  countdown(n - 1)
}

function countdown(n) {
  if (n <= 0) return
  console.log(n)
  countdown(n - 1)
}

function half(n) {
  if (n === 1) return 0
  return 1 + half(Math.floor(n / 2))
}

half(0)

function half(n) {
  if (n <= 1) return 0
  return 1 + half(Math.floor(n / 2))
}

function search(lo, hi) {
  if (lo > hi) return -1
  const mid = Math.floor((lo + hi) / 2)
  return search(mid + 1, hi)
}

search(0, 1000000)

About 20 frames.

function countFiles(dir) {
  let total = dir.files.length
  for (const sub of dir.folders) {
    total += countFiles(sub)
  }
  return total
}

function countFiles(root) {
  const pending = [root]
  let total = 0
  while (pending.length > 0) {
    const dir = pending.pop()
    total += dir.files.length
    for (const sub of dir.folders) {
      pending.push(sub)
    }
  }
  return total
}

function isEven(n) {
  if (n === 0) return true
  return isOdd(n - 1)
}

function isOdd(n) {
  if (n === 0) return false
  return isEven(n - 1)
}

isEven(100000)

It overflows. Both calls are in tail position, so a language with tail-call elimination would run it in constant space, but JavaScript engines do not eliminate them.

What gets asked, and what a good answer sounds like

Say these out loud rather than reading them. The gap between knowing something and being able to say it is the thing interviews measure.