日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
Scala：尾遞歸的跟蹤調(diào)用及其局限

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

 
 
 
      
  
  
  1. def approximate(guess: Double): Double =  
    2.   
  
  
  2.  if (isGoodEnough(guess)) guess  
    3.   
  
  
  3.  else approximate(improve(guess))  
    4.

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

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

 
 
 
      
  
  
  1. def approximateLoop(initialGuess: Double): Double = {  
    2.   
  
  
  2.  var guess = initialGuess  
    3.   
  
  
  3.  while (!isGoodEnough(guess))  
    4.   
  
  
  4.   guess = improve(guess)  
    5.   
  
  
  5.  guess  
    6.   
  
  
  6. }  
    7.

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

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

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

跟蹤尾遞歸函數(shù)

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

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

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

 
 
 
      
  
  
  1. scala> boom(3)  
    2.   
  
  
  2. java.lang.Exception: boom!  
    3.   
  
  
  3.  at .boom(< console>:5)  
    4.   
  
  
  4.  at .boom(< console>:6)  
    5.   
  
  
  5.  at .boom(< console>:6)  
    6.   
  
  
  6.  at .boom(< console>:6)  
    7.   
  
  
  7.  at .< init>(< console>:6)  
    8.   
  
  
  8. ...  
    9.

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

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

你會得到：

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

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

 
 
 
      
  
  
  1. -g:notailcalls 
    2.

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

 
 
 
      
  
  
  1. scala> bang(5)  
    2.   
  
  
  2. java.lang.Exception: bang!  
    3.   
  
  
  3.  at .bang(< console>:5)  
    4.   
  
  
  4.  at .bang(< console>:5)  
    5.   
  
  
  5.  at .bang(< console>:5)  
    6.   
  
  
  6.  at .bang(< console>:5)  
    7.   
  
  
  7.  at .bang(< console>:5)  
    8.   
  
  
  8.  at .bang(< console>:5)  
    9.   
  
  
  9.  at .< init>(< console>:6)  
    10.   
  
  
  10. ...  
    11.

尾調(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)用：

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

尾遞歸的局限

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

 
 
 
      
  
  
  1. def isEven(x: Int): Boolean =  
    2.   
  
  
  2.  if (x == 0) true else isOdd(x - 1)  
    3.   
  
  
  3. def isOdd(x: Int): Boolean =  
    4.   
  
  
  4.  if (x == 0) false else isEven(x - 1)  
    5.

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

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

funValue變量指向一個實質(zhì)是包裝了nestedFun的調(diào)用的函數(shù)值。當你把這個函數(shù)值應用到參數(shù)上，它會轉(zhuǎn)向把nestedFun應用到同一個參數(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允許的重復參數(shù)
  2. 學習Scala的閉包
  3. Scala的偏應用函數(shù)
  4. Scala：函數(shù)文本的短格式和占位符語法
  5. 介紹Scala的***類函數(shù)

文章題目：Scala：尾遞歸的跟蹤調(diào)用及其局限
瀏覽地址：http://www.dlmjj.cn/article/djejpoh.html