Scala：尾遞歸的跟蹤調(diào)用及其局限
在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)美和簡明的方案。如果方案是尾遞歸，就無須付出任何運(yùn)行期開銷。
跟蹤尾遞歸函數(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的一個堆?？蚣??；蛟S你會認(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)更加先進(jì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)閱讀】
