How to avoid Stack overflow error on recursion
Updated:
The reason behind
Recursion is a powerful form of loop which repeats itself in similar form, but it should have terminal condition to prevent endless loop. Last time, we even use it with the combination of setTimeout
to prevent “Not responsive script” warning of long running loop.
However, normal recursion can possibly generate “Stack overflow” error if it repeats itself too many times. Let’s see a famous recursion example in math, factorial
.
1 | function factorial(n) { |
How does the stack looks like? Why is its size exceeded?

Here introduces a term called Execution Context and you can read more following the link. Simply say, every times a function is called, an execution context is created. Hence, they are stacked together and increase as the recursion goes deeper. You can imagine the stack size of factorial(32768)
given this from factorial(3)
.
Tail call elimination comes to rescue
Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination.
Tail call elimination can be applied if we rewritten factorial
in tail recursion style as below.
1 | function factorial(n) { |
However, the tail call optimization can only be supported until ECMAScript 6, which is not yet available in many JS engines. (Notes: Looks like Firefox already supports and it’s gonna be ready in Node.js V8 soon.)
Trampoline
What is Trampoline?
a trampoline is a loop that iteratively invokes thunk-returning functions (continuation-passing style).
…
Programmers can use trampolined functions to implement tail-recursive function calls in stack-oriented programming languages.
The simpliest form of trampoline is like below.
1 | function trampoline(fn) { |
The op
is a thunk-returning function. If the execution result it returns is NOT a function anymore, then the loop stops. It’s not so easy to understand the meaning of thunk from the definition in Wiki. But the explanation in Functional programming section is more clear.
Functional programming languages have also allowed programmers to explicitly generate thunks. This is done in source code by wrapping an argument expression in an anonymous function that has no parameters of its own. This prevents the expression from being evaluated until a receiving function calls the anonymous function
Hence, when we rewrite our factorial
in below style, we can use the trampoline
to replace the recursive call to even calculate factorial for 1000000. (Notes: As the simple version of trampoline detects function return for terminal condition, we have to rewrite the factorial to accept callback instead.)
1 | function thunkedFactorial(n, cb) { |
Other thoughts?
You may question that, since trampoline
is actually a loop, it might cause the “Not responsive script” warning as well. Yes, you are right. That is why we can use the setTimeout
trick again as well. :)
1 | function factorial(n, cb) { |