Scala尾遞歸的跟蹤調用及局限方法是什么

這篇文章主要講解了“Scala尾遞歸的跟蹤調用及局限方法是什么”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Scala尾遞歸的跟蹤調用及局限方法是什么”吧！

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

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

這樣的函數，帶合適的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的一個堆棧框架。或許你會認為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編譯器能執行尾調用優化，但在這個例子里做不到。因此，尾調用優化受限于方法或嵌套函數在***一個操作調用本身，而沒有轉到某個函數值或什么其它的中間函數的情況。

感謝各位的閱讀，以上就是“Scala尾遞歸的跟蹤調用及局限方法是什么”的內容了，經過本文的學習后，相信大家對Scala尾遞歸的跟蹤調用及局限方法是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！