The Call Stack is Not an Infinite Resource — How to Avoid a Stack Overflow in JavaScript
Use JavaScript to understand how recursion can lead to a stack overflow and tricks to prevent it from happening
The call stack is not an infinite resource. This is especially true when performing deep recursion. Functions calls within functions are placed on the call stack further up, which means each recursive call sits on the call stack, waiting to be executed.
The call stack size is not fixed in Javascript, but it’s not huge. Let’s take a look at a trivial example:
let ct = 0;
const MAX = 100_000const recurse = () => {
if (++ct > MAX) return
recurse()
}try {
recurse()
} catch (e) {
console.error({ ct, e })
}
If I run this in Node.js I get the following output:
{
ct: 15711,
e: RangeError: Maximum call stack size exceeded
at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:4:17)
at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
}A stack overflow occurs on the 15,711th iteration. The following are some tricks to prevent this from happening.
setTimeout
The setTimeout function schedules a function call to be handled by the event loop at some future point in time. True recursion isn’t happening in this case: the inner “recursive” function will execute, but the outer function will by then have returned, and thus not longer in the event message queue (the one that tells the event loop what to do and when to do it).
The setTimeout method takes two parameters: a function and a time delay (in milliseconds). The delay can be zero milliseconds, so function execution can occur “immediately”. Let’s try it:
let ct = 0;
const MAX = 100_000const recurse = (cb) => {
if (++ct > MAX) {
return cb(ct)
}
setTimeout(() => recurse(cb), 0)
}try {
const then = process.hrtime.bigint();recurse((ct) => {
const now = process.hrtime.bigint();
const nanos = now - then
const runtime = Number(nanos) / 1_000_000_000
ct--
console.log({ ct, runtime });
})
} catch (e) {
console.error({ ct, e })
}
This program outputs the execution time and iteration count. Results are:
{ct: 100000, runtime: 144.47516928 }So this avoids the call stack overflow, but sort of slow, don’t you think?
setImmediate
Even though setTimeout can take 0ms as the second argument, it’s not as fast as calling setImmediate:
let ct = 0;
const MAX = 100_000const recurse = (cb) => {
if (++ct > MAX) {
return cb(ct)
}
setImmediate(() => recurse(cb))
}try {
const then = process.hrtime.bigint();recurse((ct) => {
const now = process.hrtime.bigint();
const nanos = now - then
const runtime = Number(nanos) / 1_000_000_000
ct--
console.log({ ct, runtime });
})
} catch (e) {
console.error({ ct, e })
}
The execution time for this program is much, much faster than the last:
{ ct: 100000, runtime: 0.295789227 }A fraction of a second, instead of 144+! Why?
The function execute by way of setImmediate aren’t scheduled like with setTimeout. Instead, it executes immediately after all Input/Output handers have executed. Event loop handling in JavaScript has been well-explained elsewhere, like here, and this post is about avoiding call stack overflow.
nextTick
When executing within the Node.js environment, there is another resource available to avoid stack overflow: process.nextTick(). The process object is a global, much like the window object in a browser. The nextTick method executes the function at the first opportunity, bypassing the event message queue.
let ct = 0;
const MAX = 100_000const recurse = (cb) => {
if (++ct > MAX) {
return cb(ct)
}
process.nextTick(() => recurse(cb))
}try {
const then = process.hrtime.bigint();recurse((ct) => {
const now = process.hrtime.bigint();
const nanos = now - then
const runtime = Number(nanos) / 1_000_000_000
ct--
console.log({ ct, runtime });
})
} catch (e) {
console.error({ ct, e })
}
The result is:
{ ct: 100000, runtime: 0.109725787 }So nextTick is 60–70% faster than setImmediate for this trivial code example.
looping
Instead of using recursion, it is possible to convert the recursive calls to loops. For the trivial examples shown so far, that’s an easy task.
Sometimes, though, recursion can be deeply nested. Let’s say function A calls function B calls function C which may call function B again or function A. Now you have A->B->C->B|A recursion, and converting that type of recursion to a loop might not be so easy.
Instead of calling functions directly, the main loop can call a function through a variable. The function variable is set by each function call, and it becomes the responsibility of the loop construct to invoke each function:
let ct = 0;
const MAX = 100_000const A = () => {
fp = B;
}const B = () => {
fp = A;
}let fp = B;const then = process.hrtime.bigint();for (; ;) {if (++ct > MAX) {
const now = process.hrtime.bigint();
const nanos = now - then;const runtime = Number(nanos) / 1_000_000_000
ct--
console.log({ ct, runtime });
break;
}
fp()
continue;
}
This loop doesn’t have any functions calling functions, but each function has the responsibility to know and control what function is executed next by way of the function variable fp. This yields the fastest results yet:
{ ct: 100000, runtime: 0.015974012 }So there you have it: four ways to avoid the dreaded stack overflow.
