JavaScript 異步編程指南 - 如何用異步任務(wù)解決遞歸棧溢出?
在編程中使用遞歸,如果沒有控制好代碼的執(zhí)行邊界或過多層級的遞歸調(diào)用,就會造成棧溢出錯誤,就像下面展示的這段錯誤堆棧。
- RangeError: Maximum call stack size exceeded
- at fn (/xxx/test.js:2:3)
- at fn (/xxx/test.js:7:10)
為什么遞歸會造成堆棧溢出?
函數(shù)運(yùn)行會有一個執(zhí)行棧,每次調(diào)用會做入棧操作,保存一些局部變量、函數(shù)參數(shù)、當(dāng)前程序的運(yùn)行狀態(tài)等,這些信息都會保存在??臻g里,而??臻g的存儲是一段連續(xù)的內(nèi)存地址,有大小限制。
以下是一段遞歸調(diào)用的簡單示例。
- function fn(i) {
- i--;
- if (i < 1) {
- return;
- }
- return fn(i);
- }
- fn(20000);
以下通過 gif 動圖展示了上述代碼的執(zhí)行過程,當(dāng)在主線程上調(diào)用 fn 函數(shù)后,不斷的做壓棧操作,而??臻g也在不斷的增加,直到達(dá)到最大的??臻g限制,程序報錯 “Maximum call stack size exceeded”。

javascript-recursion-stack-overflow (1).gif
使用異步解決棧溢出問題解
決遞歸造成的棧溢出問題,一種方法是可以使用 JavaScript 中的異步任務(wù),也是借助了事件循環(huán)機(jī)制。宏任務(wù)有 setTimeout、Node.js 環(huán)境下的 setImmediate,微任務(wù)有 Promise、queueMicrotask。
修改代碼,在 setTimeout 函數(shù)里遞歸調(diào)用。
- function fn(i) {
- i--;
- if (i < 1) {
- return;
- }
- setTimeout(function() {
- fn(i);
- }, 0);
- }
- fn(20000);
運(yùn)行效果如下所示:

javascript-async-recursion.gif
當(dāng)首次調(diào)用 fn(2000) 時,創(chuàng)建一個調(diào)用棧,函數(shù)內(nèi)部調(diào)用 setTimeout 函數(shù)后會立即返回,當(dāng)前的調(diào)用棧就結(jié)束了,傳入的回調(diào) **function() { fn(i) }** 還沒有執(zhí)行,主線程不會在這里等待,也不會形成層層嵌套的調(diào)用鏈。
定時器函數(shù)由宿主環(huán)境實(shí)現(xiàn),當(dāng)將來的某個時間點(diǎn)計時器時間到達(dá)后,宿主環(huán)境會將 timer 函數(shù)封裝為一個事件放入 “任務(wù)隊列” 中,事件循環(huán)檢測到任務(wù)隊列有可執(zhí)行的任務(wù),就拿出來執(zhí)行,之后再次調(diào)用 fn(i) 創(chuàng)建新的調(diào)用棧,反復(fù)循環(huán)。
還可以通過微任務(wù)實(shí)現(xiàn),微任務(wù)有個缺點(diǎn)是當(dāng)調(diào)度大量的微任務(wù)時雖然不會導(dǎo)致調(diào)用棧溢出,但也會導(dǎo)致和同步任務(wù)相同的性能缺陷,后面的任務(wù)得不到執(zhí)行,瀏覽器的渲染工作也會被阻止,直到所有的微任務(wù)執(zhí)行完畢。
總結(jié)
這個問題通過結(jié)合異步任務(wù)來解決遞歸造成的棧溢出問題,也可以做為事件循環(huán)的一個例子來學(xué)習(xí),更好的掌握同步任務(wù)、異步之間的調(diào)度關(guān)系。
在程序中使用遞歸還是要謹(jǐn)慎的,若控制不好邊界,很容易造成 “棧溢出”。除了改為異步任務(wù)調(diào)用外,還可將遞歸改為循環(huán)迭代、尾遞歸優(yōu)化等。