Js 不导致栈溢出的递归函数

堆栈溢出

递归函数（Recursive Function）如果调用自身次数过多，超过栈大小限制，就会导致栈溢出。

一个典型的例子是，用递归函数简陋实现斐波那契数列，如果调用参数过大，将导致栈溢出：

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)}`)
}

这种用递归函数简陋实现的斐波那契数列可能由于大量的冗余计算导致程序运行缓慢。如果输入 n 过大，可能会超过最大调用栈大小，导致栈溢出。

异步递归

不过，并非所有多次调用自身的递归函数都会导致栈溢出。

在 JavaScript 中，当每次递归调用都被放在当前执行上下文完成后运行，就会发生异步递归。 例如使用 setTimeout、setInterval 或异步函数（Promise/async/await）时。这里是一个使用 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
*/

下面是另一个使用 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)

尾递归优化是指一个函数的最后一个操作是调用另一个函数（或自身），而当前函数的栈帧可以被新函数的栈帧所替代。这可以防止每次递归调用都导致栈增长。不同的编程语言及其编译器对尾递归优化的支持各不相同。当启用优化标记时，某些编译器（如 GCC）会在某些场景下消除尾部调用。

截至 2023 年，JavaScript 环境尚未广泛支持尾递归优化。

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/