[[432656]]

在編程中使用遞歸，如果沒(méi)有控制好代碼的執(zhí)行邊界或過(guò)多層級(jí)的遞歸調(diào)用，就會(huì)造成棧溢出錯(cuò)誤，就像下面展示的這段錯(cuò)誤堆棧。

RangeError: Maximum call stack size exceeded 
    at fn (/xxx/test.js:2:3) 
    at fn (/xxx/test.js:7:10) 

為什么遞歸會(huì)造成堆棧溢出?

函數(shù)運(yùn)行會(huì)有一個(gè)執(zhí)行棧，每次調(diào)用會(huì)做入棧操作，保存一些局部變量、函數(shù)參數(shù)、當(dāng)前程序的運(yùn)行狀態(tài)等，這些信息都會(huì)保存在棧空間里，而棧空間的存儲(chǔ)是一段連續(xù)的內(nèi)存地址，有大小限制。

以下是一段遞歸調(diào)用的簡(jiǎn)單示例。

function fn(i) { 
  i--; 
  if (i < 1) { 
    return; 
  } 
  return fn(i); 
} 
fn(20000); 

以下通過(guò) gif 動(dòng)圖展示了上述代碼的執(zhí)行過(guò)程，當(dāng)在主線程上調(diào)用 fn 函數(shù)后，不斷的做壓棧操作，而?？臻g也在不斷的增加，直到達(dá)到最大的?？臻g限制，程序報(bào)錯(cuò) “Maximum call stack size exceeded”。

javascript-recursion-stack-overflow (1).gif

使用異步解決棧溢出問(wèn)題解

決遞歸造成的棧溢出問(wèn)題，一種方法是可以使用 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) 時(shí)，創(chuàng)建一個(gè)調(diào)用棧，函數(shù)內(nèi)部調(diào)用 setTimeout 函數(shù)后會(huì)立即返回，當(dāng)前的調(diào)用棧就結(jié)束了，傳入的回調(diào) **function() { fn(i) }** 還沒(méi)有執(zhí)行，主線程不會(huì)在這里等待，也不會(huì)形成層層嵌套的調(diào)用鏈。

定時(shí)器函數(shù)由宿主環(huán)境實(shí)現(xiàn)，當(dāng)將來(lái)的某個(gè)時(shí)間點(diǎn)計(jì)時(shí)器時(shí)間到達(dá)后，宿主環(huán)境會(huì)將 timer 函數(shù)封裝為一個(gè)事件放入 “任務(wù)隊(duì)列” 中，事件循環(huán)檢測(cè)到任務(wù)隊(duì)列有可執(zhí)行的任務(wù)，就拿出來(lái)執(zhí)行，之后再次調(diào)用 fn(i) 創(chuàng)建新的調(diào)用棧，反復(fù)循環(huán)。

還可以通過(guò)微任務(wù)實(shí)現(xiàn)，微任務(wù)有個(gè)缺點(diǎn)是當(dāng)調(diào)度大量的微任務(wù)時(shí)雖然不會(huì)導(dǎo)致調(diào)用棧溢出，但也會(huì)導(dǎo)致和同步任務(wù)相同的性能缺陷，后面的任務(wù)得不到執(zhí)行，瀏覽器的渲染工作也會(huì)被阻止，直到所有的微任務(wù)執(zhí)行完畢。

總結(jié)

這個(gè)問(wèn)題通過(guò)結(jié)合異步任務(wù)來(lái)解決遞歸造成的棧溢出問(wèn)題，也可以做為事件循環(huán)的一個(gè)例子來(lái)學(xué)習(xí)，更好的掌握同步任務(wù)、異步之間的調(diào)度關(guān)系。

在程序中使用遞歸還是要謹(jǐn)慎的，若控制不好邊界，很容易造成 “棧溢出”。除了改為異步任務(wù)調(diào)用外，還可將遞歸改為循環(huán)迭代、尾遞歸優(yōu)化等。