4.4　遞歸

遞歸函數是指調用自身的函數，在前文的深拷貝函數中我們就用到了遞歸函數，讓我們來回憶一下，示例如下。

上例中的函數deepCopy就是遞歸函數。

遞歸函數必須有可以終止遞歸調用的語句，否則會導致內存溢出，以一個計算階乘的函數為例，如果沒有終止遞歸的條件，這個函數將無休止地運行下去，會導致內存溢出，而“聰明”的瀏覽器則會拋出棧溢出的錯誤，示例如下。

為以上函數添加終止遞歸的條件，示例如下。

我們也可以通過arguments.callee調用函數自身，但arguments.callee性能不佳，因此，在嚴格模式下arguments.callee是無法使用的，示例如下。

在講尾遞歸之前，先了解一下函數調用堆棧的問題，這里需要引入一個概念——棧幀。

有如下一段代碼：

函數調用時會創建一個幀，幀中包含的參數和局部變量等信息形成一個棧幀。當運行的程序從當前函數A調用另外一個函數B時，就會為函數B建立一個新的棧幀，這個棧幀會被壓入函數A的棧幀。當函數B返回時，其棧幀會從函數A的棧幀中彈出，此時進入函數A的棧幀，如果函數A也返回，那么棧就空了。

再來談遞歸，遞歸的性能并不好，因為在遞歸終止前，JavaScript引擎會為每一次遞歸分配一塊內存以存儲棧幀，隨著遞歸的深入，這個棧幀也越來越龐大，也就導致遞歸占用的內存越來越多，當傳入factorial的數值增加到一定程度時，例如10 000（不同瀏覽器的內存限制不同）,瀏覽器就會因為耗盡內存而拋出棧溢出的錯誤。

尾調用是指在函數執行的最后一步調用另外一個函數并返回，因為函數返回后，其棧幀也會被彈出，因此其占用的內存也得以釋放，示例如下。

      function foo(){
          return bar()
      }

而在遞歸中進行尾調用就稱為“尾遞歸”，尾遞歸會在執行時被優化成循環形式執行，這種方式被稱為TCO（Tail Call Optimisation，尾調用優化），示例如下。

遺憾的是，大多數JavaScript引擎（V8引擎曾短暫支持過TCO，但于2017年7月從TurboFan的源碼中移除了支持TCO的代碼，Safari已經支持）并沒有實現尾遞歸的優化，所以上述代碼依舊會拋出棧溢出的錯誤。

練習

• 使用遞歸。