Stack limits & stack overflow

Why recursion can crash

A recursive function is a function that calls itself. It can call itself directly, or through other functions. The Recursion and Advanced recursion lessons show when this is useful. This lesson is about a limit. If the calls go too deep, the program crashes.

When a function calls another function, the first one is not finished yet. It waits. JavaScript keeps a small record for each waiting call. This record is called a stack frame. It holds the call's values and the place to go back to when the call ends. All the frames sit on the call stack, one on top of another. The Stack frames & calling conventions lesson shows what a frame holds.

The amount of stack space is set by the host. The host is the program that runs your JavaScript, such as a browser or Node. Inside each host is an engine: the part that runs the code. Chrome and Node use the V8 engine. Firefox uses SpiderMonkey. Safari uses JavaScriptCore.

The official rulebook for JavaScript is called ECMAScript. It says how calls and returns work. It does not say how much stack space there must be. It also does not say which error to throw when the space runs out. Each engine decides that.

1function countUntilLimit(limit) {2  let depth = 0;3  function dive() {4    depth += 1;5    if (depth === limit) return depth;6    return dive();7  }8  return dive();9}10 11console.log(countUntilLimit(3));Run

The step-through above is tiny and safe. It stops after three calls. Line 2 sets a counter, depth, to 0. Line 4 adds 1 to it. Line 6 calls dive() again, so one more call is now waiting. Line 5 is a guard: a check that stops the calls. Without a guard, the calls keep piling up until the host has no room for another frame.

The limit is space, not a number of calls

The error message says "Maximum call stack size exceeded". That sounds like a fixed number of calls. It isn't. Most engines limit the space on the stack, counted in bytes. A byte is a tiny unit of memory.

• If each frame is small, more calls fit.
• If each frame is large, fewer calls fit.

The table answers four questions about the limit. Read each row from left to right.

In Node, you can change the amount of stack space with a setting: node --stack-size=<kB>. The number is in kilobytes (kB). A kilobyte is about a thousand bytes. This setting is good for experiments. It is not a real fix for code that recurses as deep as the data a user sends.

Chrome says RangeError, Firefox says InternalError

Each engine reports a stack overflow in its own way:

• In Chrome and Node (the V8 engine), the error is a RangeError. Its message is Maximum call stack size exceeded.
• In Safari (JavaScriptCore), MDN shows the same RangeError message, with a full stop at the end.
• In Firefox (SpiderMonkey), MDN shows InternalError: too much recursion.

InternalError is not one of the standard errors in the ECMAScript rulebook. Only Firefox has it. So code that should work in every browser must not expect InternalError to exist.

The table lists each engine, the type of error it throws, and the message you will likely see.

1function measureSmallFrame() {2  let depth = 0;3  function dive() {4    depth += 1;5    return dive();6  }7  try {8    dive();9  } catch (error) {10    return { depth, name: error.name, message: error.message, range: error instanceof RangeError };11  }12}13 14function measureLargeFrame() {15  let depth = 0;16  function dive(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z) {17    const localSum = a + b + c + d + e + f + g + h + i + j + k + l + m + n + o + p + q + r + s + t + u + v + w + x + y + z;18    depth += 1;19    if (localSum === -1) throw new Error("unreachable");20    return dive(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z);21  }22  try {23    dive(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);24  } catch (error) {25    return { depth, name: error.name, message: error.message, range: error instanceof RangeError };26  }27}28 29console.log(JSON.stringify({30  node: process.versions.node,31  v8: process.versions.v8,32  small: measureSmallFrame(),33  large: measureLargeFrame(),34}));

This code has two functions. Each one calls itself until the stack is full. Line 4 and line 18 add 1 to a counter on every call. When the error comes, line 10 and line 25 save the counter, the error's name and message, and whether it is a RangeError. Line 29 prints all of it as text, so the tests can read it.

The browser messages in the table come from the MDN page InternalError: too much recursion. MDN is a well-known reference site for web developers. The facts about Node and V8 are checked by the lesson's test.

Measure the depth, but don't trust one number

You can count how many calls fit before the error. This count is the depth. A depth count helps you understand a problem. It tells you what happened in this host, for this function, right now. Don't copy the number into your app as a fixed limit.

The playground below runs two real tests in your browser:

• The small-frame function only adds 1 to a counter. Then it calls itself.
• The large-frame function takes 26 parameters and adds them up. Then it calls itself.

Expect two different numbers. Don't expect any exact value.

1function measureSmallFrame() {2  let depth = 0;3  function dive() {4    depth += 1;5    return dive();6  }7  try {8    dive();9  } catch (error) {10    return { depth, name: error.name, message: error.message };11  }12}13 14function measureLargeFrame() {15  let depth = 0;16  function dive(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z) {17    const localSum = a + b + c + d + e + f + g + h + i + j + k + l + m + n + o + p + q + r + s + t + u + v + w + x + y + z;18    depth += 1;19    if (localSum === -1) throw new Error("unreachable");20    return dive(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z);21  }22  try {23    dive(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);24  } catch (error) {25    return { depth, name: error.name, message: error.message };26  }27}

Line 4 adds 1 to the counter in the small function. Line 18 adds 1 to a separate counter in the large function. Both functions use try...catch. It runs the code in try. If that code throws an error, JavaScript jumps to the catch part instead of crashing. So the page can show the numbers, and the lesson keeps working.

Bigger frames mean fewer calls

The Node test gives both functions the same amount of stack space. The small function has almost nothing in its frame. The large function has 26 parameters and a local variable. Each large call uses more bytes, so the large function runs out of space sooner.

So a claim like "my browser handles about N calls" is not complete. You also need to know which function made N calls, and in which host.

Use a loop when the depth has no limit

Recursion is often the clearest way to walk through data shaped like a tree, where each item can hold more items. It is safe when you know the depth stays small. It is risky when the depth comes from outside your code: from users, from a server, or from imported files.

The next example uses a linked list. A linked list is a chain of objects. Each object has a value and a next property. The next property points to the next object in the chain. The last object has next: null.

1function makeDeepList(depth) {2  let node = null;3  for (let i = 0; i < depth; i += 1) {4    node = { value: 1, next: node };5  }6  return node;7}8 9function sumRecursive(node) {10  if (node === null) return 0;11  return node.value + sumRecursive(node.next);12}13 14const deepList = makeDeepList(100000);15console.log(sumRecursive(deepList));

Line 14 builds a list of 100000 objects. Line 15 calls the recursive sum. Line 11 is the problem. It calls sumRecursive again for the next object, before the current call can finish. So every object in the list adds one more waiting call.

1function makeDeepList(depth) {2  let node = null;3  for (let i = 0; i < depth; i += 1) {4    node = { value: 1, next: node };5  }6  return node;7}8 9function sumWithExplicitStack(root) {10  let total = 0;11  const pending = [root];12  while (pending.length > 0) {13    const node = pending.pop();14    if (node === null) continue;15    total += node.value;16    pending.push(node.next);17  }18  return total;19}20 21const deepList = makeDeepList(100000);22console.log(sumWithExplicitStack(deepList));

This version uses a loop instead of more calls:

1. Line 11 makes pending, an array of objects still to visit.
2. Line 13 takes the last object off the array with pop().
3. Line 15 adds its value to the total.
4. Line 16 puts the next object on the array with push().

Only one function call is waiting the whole time, and the program prints 100000. The array lives in the heap. The heap is the large area of memory where JavaScript keeps objects and arrays. It has much more room than the call stack. An array that you add to and take from at the same end is also called a stack. Because your own code manages it, it is called an explicit stack.

1const list = { value: 1, next: { value: 2, next: { value: 3, next: null } } };2 3function sumWithExplicitStack(root) {4  let total = 0;5  const pending = [root];6 7  while (pending.length > 0) {8    const node = pending.pop();9    if (node === null) continue;10    total += node.value;11    pending.push(node.next);12  }13 14  return total;15}16 17console.log(sumWithExplicitStack(list));Run

The table compares four ways to walk through deep data. Read each row from left to right.

Where this shows up in real apps

Data nested many levels deep shows up in many places:

• comment threads, with replies to replies
• category trees and menus in a shop
• page trees in a content management system (CMS), the tool a team uses to edit its website
• file explorers, with folders inside folders
• JSON files that you import
• maps of links between pages

For example, a Bengaluru events site loads a comment thread. The replies can nest much deeper than the designer expected.

1const thread = {2  text: "Bengaluru meetup",3  replies: [4    { text: "Where in Indiranagar?", replies: [] },5    { text: "Can I bring a friend?", replies: [6      { text: "Yes, register both names.", replies: [] },7      { text: "Metro is easier than parking.", replies: [] },8    ] },9  ],10};11 12function countComments(root) {13  let count = 0;14  const pending = [root];15  while (pending.length > 0) {16    const comment = pending.pop();17    if (!comment) continue;18    count += 1;19    for (const reply of comment.replies) pending.push(reply);20  }21  return count;22}23 24console.log(countComments(thread));

Line 14 puts the first comment in pending. Line 16 takes one comment off. Line 18 counts it. Line 19 puts all its replies on pending. So the deep replies wait in the array, not on the call stack. The example prints 5.

• Use recursion when you know the depth stays small.
• Use a loop with an explicit stack or a queue when the depth comes from users, a server, or imported files. A queue is an array where you add at the end and take from the front.
• Some data can point back to itself in a circle. Check for that in your own code. Don't wait for a stack overflow to stop it.
• If you change code to make it faster, measure first. The reason for a loop here is safety with deep data, not speed.
• The Tail calls lesson covers tail calls and trampolines. This lesson doesn't.

Common misconceptions

• "The limit is the same everywhere." It changes with the host, the stack space setting, the frame size, the device, and how the engine has sped up the code.
• "A stack overflow means all memory is full." The call stack and the heap are different areas of memory. An explicit stack uses the heap, so the calls don't pile up.
• "I can catch the RangeError and use it to stop a loop." By the time you catch it, some work has already happened. The stack was almost full when the error was thrown.
• "All recursion is bad." Recursion is fine when the depth is small and has a limit. The risk is depth with no limit.
• "Tail calls fix this everywhere." Tail calls and trampolines are the next lesson. Most engines don't support proper tail calls.

1let writes = 0;2function riskySave() {3  writes += 1;4  return riskySave();5}6 7try {8  riskySave();9} catch (error) {10  console.log(error instanceof RangeError);11  console.log(writes > 0);12}

In V8, this code prints true twice. The first true says the error is a RangeError. The second says writes is already more than 0. Catching the error did not undo line 3.

The table lists four ideas that are easy to mix up. Each row says what the idea means and what it is not.

Practice exercises

function countUntilLimit(limit) {
  let depth = 0;
  function dive() {
    depth += 1;
    if (depth === limit) return depth;
    return dive();
  }
  return dive();
}
console.log(countUntilLimit(3));

function makeDeepList(depth) {
  let node = null;
  for (let i = 0; i < depth; i += 1) {
    node = { value: 1, next: node };
  }
  return node;
}

function sumRecursive(node) {
  if (node === null) return 0;
  return node.value + sumRecursive(node.next);
}

const deepList = makeDeepList(100000);
console.log(sumRecursive(deepList));

const list = { value: 1, next: { value: 2, next: { value: 3, next: null } } };
function sumWithExplicitStack(root) {
  let total = 0;
  const pending = [root];
  while (pending.length > 0) {
    const node = pending.pop();
    if (node === null) continue;
    total += node.value;
    pending.push(node.next);
  }
  return total;
}
console.log(sumWithExplicitStack(list));

Check your understanding

For each question, ask two things. Is this a JavaScript rule, or something the host decides? And where is the waiting work kept?

Key takeaways

• Each waiting call uses some stack space. The space has a limit, so very deep recursion crashes.
• The limit depends on the host and on the frame size. Never count on one exact depth.
• Chrome, Node, and Safari throw a RangeError. Firefox throws InternalError: too much recursion.
• Measure the depth only to understand a problem. Catch the error only to report it, not to stop a loop.
• For deep trees, lists, and comment threads, keep the waiting work in an explicit stack or a queue.

Next: Tail calls explains proper tail calls and trampolines.