Scala尾遞歸的跟蹤調(diào)用及局限方法是什么

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

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

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

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

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

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

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

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

跟蹤尾遞歸函數(shù)

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

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

這個(gè)函數(shù)不是尾遞歸，因?yàn)樵谶f歸調(diào)用之后執(zhí)行了遞增操作。如果執(zhí)行它，你會(huì)得到預(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)

你會(huì)得到：

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

這回，你僅看到了bang的一個(gè)堆?？蚣堋；蛟S你會(huì)認(rèn)為bang在調(diào)用自己之前就崩潰了，但這不是事實(shí)。如果你認(rèn)為你會(huì)在看到堆棧跟蹤時(shí)被尾調(diào)用優(yōu)化搞糊涂，你可以用開關(guān)項(xiàng)關(guān)掉它：

-g:notailcalls

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

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的編譯后代碼實(shí)質(zhì)上與approximateLoop的編譯后代碼相同。兩個(gè)函數(shù)編譯后都是同樣的事三個(gè)Java字節(jié)碼指令。如果你看一下Scala編譯器對(duì)尾遞歸方法，approximate，產(chǎn)生的字節(jié)碼，你會(huì)看到盡管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里尾遞歸的使用局限很大，因?yàn)镴VM指令集使實(shí)現(xiàn)更加先進(jìn)的尾遞歸形式變得很困難。Scala僅優(yōu)化了直接遞歸調(diào)用使其返回同一個(gè)函數(shù)。如果遞歸是間接的，就像在下面的例子里兩個(gè)互相遞歸的函數(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)

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

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

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

感謝各位的閱讀，以上就是“Scala尾遞歸的跟蹤調(diào)用及局限方法是什么”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)Scala尾遞歸的跟蹤調(diào)用及局限方法是什么這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！