Why Your Recursion Is Lying to You in JavaScript
Recursion feels elegant, but it hides a dangerous physical limit: stack overflow. Even with correct logic and tail-recursive structure, most JavaScript runtimes like V8 and SpiderMonkey do not guarantee stack safety. I explain why relying on Tail Call Optimization is risky in production and show how iterative patterns or trampolines offer a safer, more portable alternative for handling deep recursion.
Recursion itself is not the enemy, unverified runtime assumptions are.
- ventana
A fun quote from the article, discussing a basic Fibonacci recursive implementation:
> Each call branches into two more calls, so the total number of calls grows as O(2ⁿ).
Well, no, not really. If anyone bothers counting how many recursive calls are actually made, the result is far from powers of two:
n | result | # of calls
1 | 1 | 1
2 | 1 | 3
3 | 2 | 5
4 | 3 | 9
5 | 5 | 15
6 | 8 | 25
7 | 13 | 41
8 | 21 | 67
9 | 34 | 109
10 | 55 | 177
11 | 89 | 287
12 | 144 | 465
13 | 233 | 753
14 | 377 | 1219
15 | 610 | 1973
16 | 987 | 3193
17 | 1597 | 5167
18 | 2584 | 8361
19 | 4181 | 13529
20 | 6765 | 21891
A curious person will then calculate the actual ratio:
n | result | # of calls | ratio
1 | 1 | 1 | 1
2 | 1 | 3 | 3
3 | 2 | 5 | 1.6666666666666667
4 | 3 | 9 | 1.8
5 | 5 | 15 | 1.6666666666666667
6 | 8 | 25 | 1.6666666666666667
7 | 13 | 41 | 1.64
8 | 21 | 67 | 1.6341463414634145
9 | 34 | 109 | 1.626865671641791
10 | 55 | 177 | 1.6238532110091743
11 | 89 | 287 | 1.621468926553672 […]
- RajT88
CS 101, no? Recursion is easier to write, but less performant and more risky than iteration.
- eventualcomp
no mention of dynamic programming for dealing with recursive functions? Dynamic programming was built for this, you don't even need to thrash the heap as much as that trampoline. Instantiate your array, make sure you set your base cases and loops so that you don't step in an `undefined` hole, and then recurse in reverse.
- 10000truths
The troubles of handling call stack recursion is downstream of the lack of strong tooling for static analysis of stack usage. Of the few tools available for generating a build-time call graph for an application, almost none of them can do so in a machine-readable format. AFAIK, the state of the art here is LLVM's dot-callgraph pass, and even that emits DOT rather than something more widely adopted like CSV or JSON. Outside of that, you have to build your own thing, either via runtime profiling or a custom compiler plugin.
- okzgn
Reference link: https://v8.dev/blog/modern-javascript#proper-tail-calls (Recursion, Proper tail calls, 2016)
Proper Tail Calls were implemented behind experimental flags but never shipped by default — the flags were later removed.