Recursive functions don't casue stack overflow in JS

Stack Overflow

Recursive functions can cause a stack overflow if they call themselves too many times and exceed the stack size limit.

A classic example of a recursive function that can exceed the stack size limit if called with a large input is the naive implementation of the Fibonacci sequence:

function fibonacci(n) {
  if (n < 2) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

for (let n = 0; n < 100; n++) {
  console.log(`fibo ${n}: ${fibonacci(n)}`)
}

This naive implementation of the Fibonacci sequence can cause a program to run slowly due to the large number of redundant computations. If the input n is too large, it can exceed the maximum call stack size and cause a stack overflow.

Asynchronous Recursion

However, not all recursive functions that call themselves multiple times will causing a stack overflow.

In JavaScript, asynchronous recursion can occur when each recursive call is scheduled to run after the current execution context has completed, such as when using setTimeout, setInterval, or asynchronous functions (Promise/async/await). Here's an example using setTimeout:

function asyncRecursiveFunction(n) {
  if (n > 0) {
    console.log(n);
    setTimeout(() => asyncRecursiveFunction(n - 1), 1000);
  } else {
    console.log('Done');
  }
}

asyncRecursiveFunction(5);
/*
5
4
3
2
1
Done
*/

Here's another example using Promise:

function sleep(ms) {
  return new Promise(resolve => setTimeout(resolve, ms));
}

function sleepList(ts1, ts2, sleepID = 0) {
  if (ts1 >= ts2) {
    console.log('Finished processing array');
    return;
  }

  console.log(`sleep ${sleepID} begin ${ts1}ms`);

  sleep(ts1)
    .then(s => {
      console.log(`sleep ${sleepID} end ${ts1}ms`);
      sleepList(ts1 + 1, ts2, sleepID + 1);
    });
}

sleepList(1000, 1005);
/*
sleep 0 begin 1000ms
sleep 0 end 1000ms
sleep 1 begin 1001ms
sleep 1 end 1001ms
sleep 2 begin 1002ms
sleep 2 end 1002ms
sleep 3 begin 1003ms
sleep 3 end 1003ms
sleep 4 begin 1004ms
sleep 4 end 1004ms
Finished processing array
*/

Tail Call Optimization (TCO)

Tail call optimization is a feature where the last action of a function is a call to another function (or itself), and the current function's stack frame can be replaced with the new function's stack frame. This prevents the stack from growing with each recursive call. The support for Tail Call Optimization (TCO) varies across different programming languages and their compilers. Some compilers, such as GCC, have been known to perform tail call elimination in certain cases when optimization flags are used.

As of 2023, TCO is not widely supported in JavaScript environments.

https://stackoverflow.com/questions/37224520/are-functions-in-javascript-tail-call-optimized

https://stackoverflow.com/questions/54719548/tail-call-optimization-implementation-in-javascript-engines

https://www.reddit.com/r/javascript/comments/pwwbky/askjs_why_so_little_support_for_tco_tail_call/