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

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

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

這樣的函數，帶合適的isGoodEnough和improve的實現，經常用在查找問題中。如果想要approximate函數執行得更快，你或許會被誘惑使用while循環編寫以嘗試加快它的速度，如：

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

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

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

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

跟蹤尾遞歸函數

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

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

這個函數不是尾遞歸，因為在遞歸調用之后執行了遞增操作。如果執行它，你會得到預期的：

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)  
...  

如果你現在修改了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的一個堆?？蚣??；蛟S你會認為bang在調用自己之前就崩潰了，但這不是事實。如果你認為你會在看到堆棧跟蹤時被尾調用優化搞糊涂，你可以用開關項關掉它：

-g:notailcalls 

把這個參數傳給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)  
...  

尾調用優化

approximate的編譯后代碼實質上與approximateLoop的編譯后代碼相同。兩個函數編譯后都是同樣的事三個Java字節碼指令。如果你看一下Scala編譯器對尾遞歸方法，approximate，產生的字節碼，你會看到盡管isGoodEnough和improve都被方法體調用，approximate卻沒有。Scala編譯器優化了遞歸調用：

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指令集使實現更加先進的尾遞歸形式變得很困難。Scala僅優化了直接遞歸調用使其返回同一個函數。如果遞歸是間接的，就像在下面的例子里兩個互相遞歸的函數，就沒有優化的可能性了：

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)  

同樣如果***一個調用是一個函數值你也不能獲得尾調用優化。請考慮下列遞歸代碼的實例：

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

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

【相關閱讀】

1. Scala允許的重復參數
2. 學習Scala的閉包
3. Scala的偏應用函數
4. Scala：函數文本的短格式和占位符語法
5. 介紹Scala的***類函數