Recursion is a very useful technique in programming. However, it can lead to a problem when dealing with deep recursion. Deep recursion happens when many function calls are active and waiting for the last one to finish. Each of these calls creates a new frame on the call stack. Since programs have a limit on the size of the stack, it can overflow, leading to a program crash. This happens before the function can complete all its calls and return the result.
There’s an optimization technique called Tail Call Optimization (TCO) that can help with this. When the last operation in a function is a recursive call, TCO allows reusing the same stack frame, preventing stack overflow. There are two types of TCO: Tail Call Optimizations (TCO) and Proper Tail Calls (PTC).
Unfortunately, JavaScript engines currently don’t support either TCO or PTC. This means that deep recursion in JavaScript can still lead to a “Maximum call stack size exceeded” error, at least in Node.js.
To avoid this, we can use setTimeout to schedule the recursive call after the current function ends, freeing up the current stack frame. Let’s illustrate this with an example of calculating factorials.
The common way to calculate factorials recursively is:
1
2
3
| function factorial(n) {
return (n !== 0) ? n \* factorial(n - 1) : 1;
}
|
In this code, there’s an operation after the recursive call. We can modify this code to make the recursive call the last operation:
1
2
3
4
5
6
7
| function tailFactorial(n, total = 1) {
//console.trace();
if (n === 0) {
return total;
} // proper tail call
return tailFactorial(n - 1, n \* total);
}
|
If JavaScript supported PTC, this second version would not cause a stack overflow, even with many recursive calls. However, as we can see in the following example, both versions fail when the number of recursive calls is large:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| const smallValue = 100;
const largeValue = 50000;
function runFactorial(factorialFn){
let res = factorialFn(smallValue);
console.log("factorial: " + res);
//stack overflow:
try {
res = factorialFn(largeValue);
console.log("factorial: " + res);
}
catch (ex){
console.log("Exception: " + ex.message);
//Maximum call stack size exceeded
}
}
\[factorial, tailFactorial\].forEach(fn => runFactorial(fn));
/\* Output:
factorial: 9.33262154439441e+157
Exception: Maximum call stack size exceeded
factorial: 9.332621544394418e+157
Exception: Maximum call stack size exceeded
\*/
|
We can fix this by delaying the recursive call with setTimeout. This allows the current stack frame to be freed up before the next recursive call. Here’s an example using promises:
1
2
3
4
5
6
7
8
9
10
11
12
13
| function factorialWithTimeoutAndPromise(n, total = 1, resFn){
//initial call
if (resFn === undefined){
var pr = new Promise((res, rej) => resFn = res);
}
if (n === 0){
resFn(total);
}
else{
setTimeout(() => factorialWithTimeoutAndPromise(n-1, n \* total, resFn), 0);
}
return pr;
}
|
This approach works but can be slow, even with a timeout of 0. This is because setTimeout(0) can still introduce a delay of up to 4ms.
To improve performance, we can use a hybrid approach: perform a certain number of recursive calls normally, then schedule the next call with setTimeout to clear the stack. Here’s an example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| function factorialWithTimeoutAndPromiseImproved(n, total = 1, counter = 0, resFn){
//initial call
if (resFn === undefined){
var pr = new Promise((res, rej) => resFn = res);
}
if (n === 0){
resFn(total);
}
else{
if (counter < 50){
factorialWithTimeoutAndPromiseImproved(n-1, n \* total, ++counter, resFn);
}
else{
setTimeout(() => factorialWithTimeoutAndPromiseImproved(n-1, n \* total, 0, resFn), 0);
}
}
return pr;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| (async() => {
console.log("-- using Timeout");
let options = \[
{
name: "Not optimized",
value: smallValue,
fn: factorialWithTimeoutAndPromise
},
{
name: "Not optimized",
value: largeValue,
fn: factorialWithTimeoutAndPromise
},
{
name: "Optimized",
value: smallValue,
fn: factorialWithTimeoutAndPromiseImproved
},
{
name: "Optimized",
value: largeValue,
fn: factorialWithTimeoutAndPromiseImproved
}
\];
for (let option of options) {
console.log(option.name + " factorial for: " + option.value);
let start = Date.now();
let result = await option.fn(option.value);
console.log("result: " + result);
console.log("it took " + (Date.now() - start) + "\\n");
}
})();
/\* Output:
Not optimized factorial for: 100
result: 9.332621544394418e+157
it took 132
Not optimized factorial for: 50000
result: Infinity
it took 57441
Optimized factorial for: 100
result: 9.332621544394418e+157
it took 2
Optimized factorial for: 50000
result: Infinity
it took 1187
\*/
|
You can find all the code here: into a gist
read here
I’ve read