在7.2節(jié)中，我們提到過想要把更新var的while循環(huán)轉(zhuǎn)換成僅使用val的更函數(shù)式風(fēng)格的話，有時候你可以使用遞歸。下面的例子是通過不斷改善猜測數(shù)字來逼近一個值的遞歸函數(shù)：

def approximate(guess: Double): Double =  
 if (isGoodEnough(guess)) guess  
 else approximate(improve(guess))  

51CTO編輯推薦：Scala編程語言專題

這樣的函數(shù)，帶合適的isGoodEnough和improve的實現(xiàn)，經(jīng)常用在查找問題中。如果想要approximate函數(shù)執(zhí)行得更快，你或許會被誘惑使用while循環(huán)編寫以嘗試加快它的速度，如：

def approximateLoop(initialGuess: Double): Double = {  
 var guess = initialGuess  
 while (!isGoodEnough(guess))  
  guess = improve(guess)  
 guess  
}  

兩種approximate版本哪個更好？就簡潔性和避免var而言，***個，函數(shù)式的勝出。但是否指令式的方式或許會更有效率呢？實際上，如果我們測量執(zhí)行的時間就會發(fā)現(xiàn)它們幾乎完全相同！這可能很令人驚奇，因為遞歸調(diào)用看上去比簡單的從循環(huán)結(jié)尾跳到開頭要更花時間。

然而，在上面approximate的例子里，Scala編譯器可以應(yīng)用一個重要的優(yōu)化。注意遞歸調(diào)用是approximate函數(shù)體執(zhí)行的***一件事。像approximate這樣，在它們***一個動作調(diào)用自己的函數(shù)，被稱為尾遞歸：tail recursive。Scala編譯器檢測到尾遞歸就用新值更新函數(shù)參數(shù)，然后把它替換成一個回到函數(shù)開頭的跳轉(zhuǎn)。

道義上你不應(yīng)羞于使用遞歸算法去解決你的問題。遞歸經(jīng)常是比基于循環(huán)的更優(yōu)美和簡明的方案。如果方案是尾遞歸，就無須付出任何運行期開銷。

跟蹤尾遞歸函數(shù)

尾遞歸函數(shù)將不會為每個調(diào)用制造新的堆棧框架；所有的調(diào)用將在一個框架內(nèi)執(zhí)行。這可能會讓檢查程序的堆棧跟蹤并失敗的程序員感到驚奇。例如，這個函數(shù)調(diào)用自身若干次之后拋出一個異常：

def boom(x: Int): Int =  
 if (x == 0) throw new Exception("boom!")  
 else boom(x - 1) + 1 

這個函數(shù)不是尾遞歸，因為在遞歸調(diào)用之后執(zhí)行了遞增操作。如果執(zhí)行它，你會得到預(yù)期的：

scala> boom(3)  
java.lang.Exception: boom!  
 at .boom(< console>:5)  
 at .boom(< console>:6)  
 at .boom(< console>:6)  
 at .boom(< console>:6)  
 at .< init>(< console>:6)  
...  

如果你現(xiàn)在修改了boom從而讓它變成尾遞歸：

def bang(x: Int): Int =  
 if (x == 0) throw new Exception("bang!")  
 else bang(x 1)  

你會得到：

scala> bang(5)  
java.lang.Exception: bang!  
 at .bang(< console>:5)  
 at .< init>(< console>:6)  
...  

這回，你僅看到了bang的一個堆棧框架。或許你會認(rèn)為bang在調(diào)用自己之前就崩潰了，但這不是事實。如果你認(rèn)為你會在看到堆棧跟蹤時被尾調(diào)用優(yōu)化搞糊涂，你可以用開關(guān)項關(guān)掉它：

-g:notailcalls 

把這個參數(shù)傳給scala的shell或者scalac編譯器。定義了這個選項，你就能得到一個長長的堆棧跟蹤了：

scala> bang(5)  
java.lang.Exception: bang!  
 at .bang(< console>:5)  
 at .bang(< console>:5)  
 at .bang(< console>:5)  
 at .bang(< console>:5)  
 at .bang(< console>:5)  
 at .bang(< console>:5)  
 at .< init>(< console>:6)  
...  

尾調(diào)用優(yōu)化

approximate的編譯后代碼實質(zhì)上與approximateLoop的編譯后代碼相同。兩個函數(shù)編譯后都是同樣的事三個Java字節(jié)碼指令。如果你看一下Scala編譯器對尾遞歸方法，approximate，產(chǎn)生的字節(jié)碼，你會看到盡管isGoodEnough和improve都被方法體調(diào)用，approximate卻沒有。Scala編譯器優(yōu)化了遞歸調(diào)用：

public double approximate(double);  
 Code:  
  0: aload_0  
  1: astore_3  
  2: aload_0  
  3: dload_1  
  4: invokevirtual #24; //Method isGoodEnough:(D)Z  
  7: ifeq 12 
  10: dload_1  
  11: dreturn  
  12: aload_0  
  13: dload_1  
  14: invokevirtual #27; //Method improve:(D)D  
  17: dstore_1  
  18: goto 2 

尾遞歸的局限

Scala里尾遞歸的使用局限很大，因為JVM指令集使實現(xiàn)更加先進的尾遞歸形式變得很困難。Scala僅優(yōu)化了直接遞歸調(diào)用使其返回同一個函數(shù)。如果遞歸是間接的，就像在下面的例子里兩個互相遞歸的函數(shù)，就沒有優(yōu)化的可能性了：

def isEven(x: Int): Boolean =  
 if (x == 0) true else isOdd(x - 1)  
def isOdd(x: Int): Boolean =  
 if (x == 0) false else isEven(x - 1)  

同樣如果***一個調(diào)用是一個函數(shù)值你也不能獲得尾調(diào)用優(yōu)化。請考慮下列遞歸代碼的實例：

val funValue = nestedFun _  
def nestedFun(x: Int) {  
 if (x != 0) { println(x); funValue(x - 1) }  
}  

funValue變量指向一個實質(zhì)是包裝了nestedFun的調(diào)用的函數(shù)值。當(dāng)你把這個函數(shù)值應(yīng)用到參數(shù)上，它會轉(zhuǎn)向把nestedFun應(yīng)用到同一個參數(shù)，并返回結(jié)果。因此你或許希望Scala編譯器能執(zhí)行尾調(diào)用優(yōu)化，但在這個例子里做不到。因此，尾調(diào)用優(yōu)化受限于方法或嵌套函數(shù)在***一個操作調(diào)用本身，而沒有轉(zhuǎn)到某個函數(shù)值或什么其它的中間函數(shù)的情況。（如果你還不能完全明白尾遞歸，參見8.9節(jié)）。

【相關(guān)閱讀】

1. Scala允許的重復(fù)參數(shù)
2. 學(xué)習(xí)Scala的閉包
3. Scala的偏應(yīng)用函數(shù)
4. Scala：函數(shù)文本的短格式和占位符語法
5. 介紹Scala的***類函數(shù)