在 Scala 函數(shù)式編程的世界里，因?yàn)閺?qiáng)調(diào)不可變性，所以我們需要盡量減少命令式編程的 while 循環(huán)的使用（即在可能的情況下盡量避免迭代。Scala 的 for 較為特殊，屬于 Filter-Map-Reduce 模式的語法糖，以后有機(jī)會(huì)單獨(dú)聊一聊）。

但是這樣，熟悉 Java 的朋友們就馬上想到一個(gè)問題——棧溢出。即對(duì)于需要循環(huán)大量次數(shù)的代碼，如果換為遞歸實(shí)現(xiàn)，在 Java 中很容易就會(huì)導(dǎo)致棧溢出的 OOM 異常。

其原因就在于 Java 虛擬機(jī)中，對(duì)于執(zhí)行的遞歸方法，會(huì)在 JVM 棧中保存之前每一級(jí)遞歸調(diào)用的方法棧幀。只有當(dāng)遞歸走到最后一步時(shí)，才會(huì)開始一級(jí)一級(jí)地將棧幀彈出并返回值。那么在前面壓棧的過程中，如果遞歸次數(shù)過于多，就會(huì)導(dǎo)致棧溢出的問題。

那么為了鼓勵(lì)函數(shù)式編程的寫法，Scala 必然需要解決遞歸棧溢出的問題。Scala 其實(shí)也并不能解決所有的遞歸棧溢出問題，只是針對(duì)其中一部分有優(yōu)化。解決方式就是本文的主題：Scala 編譯器針對(duì)尾遞歸的優(yōu)化。

1 尾遞歸

尾遞歸（tail-recursive）指的就是遞歸方法里的最后一條指令是遞歸調(diào)用的情況。在 Scala 中，尾遞歸會(huì)被優(yōu)化成類似 while 循環(huán)而不是一系列遞歸調(diào)用，這種方式可以對(duì)遞歸進(jìn)行優(yōu)化，從而在整個(gè)遞歸過程中只占用一個(gè)棧幀。該過程被稱為“尾部調(diào)用優(yōu)化（tail call optimization）”或簡(jiǎn)稱 TCO。

考慮如下遞歸計(jì)算整數(shù)序列之和的方法：

該方法無法被優(yōu)化，因?yàn)橛?jì)算過程的最后一步是加法，而不是遞歸調(diào)用。不過稍微調(diào)整變換一下就可以被優(yōu)化了：

部分和（ partial sum ) 被作為參數(shù)傳遞，用 sum2(xs, 0) 的方式調(diào)用該方法。由于計(jì)算過程的最后一步是遞歸地調(diào)用同一個(gè)方法，因此它可以被變換成跳回到方法頂部的循環(huán)。Scala 編譯器會(huì)自動(dòng)對(duì)第二個(gè)方法應(yīng)用“尾遞歸” 優(yōu)化。

如果你調(diào)用 sum(1 to 1000000) 就會(huì)得到一個(gè)棧溢出錯(cuò)誤（至少對(duì)于默認(rèn)棧大小的 JVM 而言如此）；但，sum2(1 to 1000000, 0) 將返回序列之和 500000500000。

遺憾的是，JVM 并不能直接支持 TCO，所以 Scala 需要在編譯期間采用一些技巧來將尾遞歸調(diào)用編譯降級(jí)為與迭代相同的字節(jié)碼。簡(jiǎn)單來說，那就是原本將使用 invokevirtual 指令調(diào)用自身的字節(jié)碼，轉(zhuǎn)變成了 goto 指令調(diào)回代碼塊頭上，這樣就避免了把對(duì)自身調(diào)用壓棧。

Scala 還為尾遞歸編譯期的優(yōu)化提供了一個(gè)注解 @scala.annotation.tailrec，該注解可以置于打算采用尾遞歸方式調(diào)用的函數(shù)上。如果該函數(shù)的遞歸調(diào)用并沒有發(fā)生在一個(gè)尾部位置，那么編譯器將會(huì)產(chǎn)生一個(gè)錯(cuò)誤。

比較典型的容易誤認(rèn)為可以優(yōu)化，但其實(shí)不能優(yōu)化的幾個(gè)情況：

1. 兩個(gè)不同方法相互在最后一條指令遞歸調(diào)用（后面會(huì)提到如何解決）

2. 非 public 方法（為了防止子類把父類的方法覆蓋成非尾遞歸的版本）

3. 遞歸屬于某個(gè) try/catch 塊

所以為了保證尾遞歸一定能在編譯期得到優(yōu)化的話，切記加上 @scala.annotation.tailrec。

有人可能會(huì)有這樣的疑問：既然最終 Scala 編譯器會(huì)在編譯期將尾遞歸優(yōu)化成 while 循環(huán)，那為什么我們鼓勵(lì)在 Scala 中使用遞歸而不是直接使用 while 循環(huán)呢？其實(shí)這里主要的目的，還是為了更好地方便程序員使用函數(shù)式編程的方式書寫代碼，消除了語言中的可變性來源。一般情況下，遞歸可以將復(fù)雜的問題分解成較小的問題，使推理和解決變得容易。遞歸也和不變性配合默契，遞歸函數(shù)給我們提供了一種很好的方法來管理改變的狀態(tài)而不使用可變數(shù)據(jù)結(jié)構(gòu)或重新賦值變量。因此，引入尾遞歸優(yōu)化和鼓勵(lì)使用遞歸還是有意義的。（當(dāng)然，最終選擇使用迭代還是遞歸實(shí)現(xiàn)，還是取決于程序員自己和使用場(chǎng)景本身，Scala 只是豐富了選擇的余地）

2 相互遞歸

前面提到 Scala 中的尾遞歸優(yōu)化是比較受限的，比如兩個(gè)相互遞歸的函數(shù)，Scala 就沒辦法直接優(yōu)化它們。例如：

但是，其實(shí)在 Scala 中，我們?nèi)匀豢梢酝ㄟ^使用特定方式來重寫方法來使得編譯器可以優(yōu)化該相互遞歸。具體來說，就是 scala.util.control.TailCalls 中提供了 tailcall() 方法和 done() 方法，前者會(huì)產(chǎn)生相互遞歸的調(diào)用，而后者供我們?cè)谕瓿蛇f歸時(shí)調(diào)用。這個(gè)優(yōu)化技巧也被稱為蹦床（trampoline）。

聽起來很玄乎，看上去卻很簡(jiǎn)單。我們可以將上面的代碼改成如下：

這樣處理后，尾遞歸函數(shù)的結(jié)果不再是直接返回的，而是被包裝在一個(gè) TailRec 類型中。為了在最后取得結(jié)果，我們可以在最后返回上調(diào)用 result() 函數(shù)：

這樣，在處理大型數(shù)字時(shí)也不會(huì)出現(xiàn)棧溢出的錯(cuò)誤。

通過閱讀源碼，我們可以看出，實(shí)際上主要被優(yōu)化了的邏輯是在 TailRec 中的 ?result() 方法中。利用 TailCalls 的 tail() 和 done() 方法轉(zhuǎn)換的樣本類 Call 和 Done，將相互調(diào)用轉(zhuǎn)換成了可以被編譯器優(yōu)化的尾遞歸：

具體原理，大家可以參考源碼自行閱讀（上面貼出來的代碼沒有 TailRec 的 flatMap、map 方法等。其還提供了一個(gè)獲取是否有下一步遞歸的方法 resume，這里也沒有貼出來）。

源碼中還提供了一個(gè)利用蹦床實(shí)現(xiàn)的斐波那契數(shù)列示例：