↩ back to Guides

How Deep Can You Recurse?

Every page on this site that labels a recursive algorithm's space cost O(n) or O(log n) means something concrete and physical by it: each call that hasn't returned yet keeps a stack frame alive, and a JS engine has a finite amount of stack memory to hold them in. That label isn't just notation — push it far enough and it becomes a literal RangeError: Maximum call stack size exceeded. This page measures that boundary directly: first in your own browser, then against three reference implementations already live elsewhere on this site.

Try it: find your browser's real limit

There's no single correct number here — the answer is set by your browser's JS engine and however much stack memory it's been handed, not by anything the JavaScript language guarantees. Click below and this page will binary-search, live, for the deepest two trivial functions can recurse in your browser right now before either one throws: one ordinary recursive function, and one written in tail-call form — its own recursive call is the very last thing it does, the specific shape the language spec permits an engine to optimize into a loop internally.

Run it a few times — in V8-based engines, each row's own number can jump between two nearby values from run to run (ordinary JIT noise: which tier the function has been compiled to changes how much stack one of its frames actually costs), so don't expect either row to be perfectly stable on repeat clicks. What to actually look for: if real tail-call elimination were happening, the tail-call-form row wouldn't fail at any depth you could practically reach at all, instead of landing in the same rough range as the ordinary version. Two numbers of the same general size is itself the sign this engine isn't eliminating the call — matching what repeated measurement in Node (V8) shows for the identical two functions (see Pitfalls).

Depth is not the same resource as total calls

A loop's variables live in one stack frame for the whole loop. A recursive call is different: the outer call is still waiting for the inner one to return, so its frame has to stay alive too — frames nest exactly as deep as the recursion does. That nesting depth, the maximum number of frames alive at once, is the number that can exhaust the stack. It has nothing to do with how many calls happen in total — a function can make an astronomical number of calls while never nesting more than a few dozen deep, or it can make very few calls while nesting dangerously deep. The two are independent, easy to conflate, and worth telling apart directly:

Every row above was counted by actually running the function, not computed from the closed form alone — though the closed form (2n+1−1 calls, n+1 depth) matches exactly at every n tried. Total calls explodes exponentially; depth climbs by exactly one per level, no matter how many siblings each level spawns. This is the shape naive, unmemoized recursion over overlapping subproblems takes before memoization is introduced — see Choosing a Dynamic Programming Approach for what replaces it — and it's also why "exponential time" and "deep recursion" are not the same worry: the first one makes your program slow, possibly unusably slow, long before the second one ever has a chance to crash it.

Three real recursive implementations, measured

All three functions below are copied verbatim from their own pages — nothing simplified or re-derived for this guide. Press the button and all three run live, in your browser, against the exact same code that page ships.

Merge Sort splits in half every call, so its depth is ⌈log₂ n⌉ + 1 regardless of input order — at two million elements that's still only 22 levels deep, nowhere near any realistic stack limit. The row above instruments the real mergeSort/merge functions from that page with a depth counter only; the sort logic itself is untouched.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

Quicksort's own Pitfalls section already names the problem: its last-element-pivot reference implementation recurses O(n) deep on an already-sorted (or reverse-sorted) array, instead of the O(log n) a balanced split would give. That page frames the cost as O(n²) time — true, but the second row above shows the other half of the same bug: the recursion depth it causes is large enough to exhaust the real call stack outright, not just run slowly. The third row runs the identical function, unmodified, on a randomly ordered array of that exact same crashing size — same code, same n, and it completes without error, because nothing forces the recursion anywhere near that deep when the input isn't adversarial.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1);
  quickSort(arr, p + 1, hi);
  return arr;
}

Measured once in Node v20.20.2, for reference (your browser's own numbers from the demo above will differ — that's the point, not a discrepancy to resolve): the sorted-input case was safe up to n = 6,959 and failed at n = 6,960; the same n = 6,960 in random order completed with no error at all.

N-Queens's own Complexity section already states its recursion stack cost as O(N) — the same shape, in the abstract, as quicksort's dangerous case. It never actually threatens the stack in practice, though, because a second constraint runs out first: the search itself is exponential in time. Measured directly against the real solveNQueens reference implementation in Node: N = 12 takes 237 ms, N = 13 takes 1.28 s, N = 14 takes 8.1 s — and the recursion is only 14 frames deep the entire time, nowhere near the tens of thousands of frames either demo above shows this engine can actually hold. By the time N is large enough for depth to matter, solving it would already take longer than anyone is willing to wait.

Pitfalls

The safe number is a property of the engine, not the language. Nothing in the ECMAScript spec guarantees any minimum call stack depth at all — "how deep can I recurse" has no fixed answer the way "is this array sorted" does. Treat any specific number quoted for it, including every number on this page, as a measurement taken in one engine at one moment, not a constant to hardcode into real code.

V8 does not implement proper tail calls, even though the spec defines them for exactly this shape. ES2015 specifies that an engine may optimize a call sitting in true tail position into a loop, reusing the caller's frame instead of stacking a new one. Measured across six repeated runs in Node v20.20.2 with the two functions from the "Try it" demo above: both the ordinary version and the tail-call-shaped version failed somewhere in the same narrow band, either n = 12,800 or n = 15,656 depending on the run — the same two values, shared by both functions, never one consistently ahead of the other. That's ordinary JIT-tiering noise, not tail-call elimination: real elimination would mean the tail-call version never fails at any depth worth testing, not that it fails in the same narrow range as the ordinary version. Rewriting a recursive function into tail form does not, on its own, save it from this limit in the engine that builds and verifies every demo on this site — and most browsers in general use today are also built on V8. Don't assume reshaping a recursive algorithm into tail form fixes a real depth problem without measuring it, the same way the demo above lets you measure your own browser instead of trusting this paragraph's specific numbers for Node.

A recursive reference implementation's documented space bound only describes the worst case over all inputs — not the input you're about to feed it. Quicksort and N-Queens above share the identical O(n) stack-space label in their own Complexity sections, yet one crashes at a size well within normal use and the other never comes close for any size anyone would actually run. The label alone can't tell you which situation you're in; the input shape and the other costs it's competing against can.

See How Fast Is Big-O? for the same measure-it-rather-than-trust-the-label approach applied to running time instead of stack depth, and The Master Theorem, Explained for how a divide-and-conquer recurrence's shape — the same a/b split that keeps Merge Sort's depth at O(log n) above — determines its time bound too.