爲什麼Scala編譯器沒有標誌這似乎不是一個尾遞歸函數？

我已標記的方法sameLength檢查和優化尾遞歸。我覺得在同一長度方法中的最後一次操作是不一樣的。這是& &。該& &是其他子句。爲什麼編譯器不標記這個。由於編譯器沒有標記它，我假設它確實是尾遞歸的。有人可以爲我定義尾遞歸嗎？我腦海中有一個錯誤的定義。爲什麼Scala編譯器沒有標誌這似乎不是一個尾遞歸函數？

import scala.annotation.tailrec 


    object TestTailRec extends App{ 

    @tailrec 
    def sameLength[T](xs: List[T], ys: List[T]) : Boolean = { 
     if(xs.isEmpty) ys.isEmpty 
     else ys.nonEmpty && sameLength(xs.tail, ys.tail) 
    } 

    println(sameLength(List(1,2,3), List(1,2,3))) 

    }

來源

2016-02-15 Mike

我不知道這是否是編譯器做什麼，但布爾表達式是由「短路」方法計算：如果ys.nonEmpty是假然後沒有必要計算sameLength。如果是真的，那麼它將返回sameLength的結果，使得它確實尾遞歸 – Eduardo

讓我們重構你的方法一點，而不改變其含義：

def sameLength[T](xs: List[T], ys: List[T]) : Boolean = { 
    if(xs.isEmpty) ys.isEmpty 
    else if (ys.isEmpty) false else 
    sameLength(xs.tail, ys.tail) 
}

我認爲這是現在很清楚，這是尾遞歸

來源

2016-02-15 20:11:26

The spec定義Boolean的&&方法。

由於Boolean是一個值類，if/else表達式被內聯。

由於p參數爲名稱，這不是第一次評估。

你的直覺是通過嚴格的版本證實：

scala> @tailrec def f(i: Int): Boolean = false & f(i) 
<console>:16: error: could not optimize @tailrec annotated method f: it contains a recursive call not in tail position

來源

2016-02-16 02:22:19

爲什麼Scala編譯器沒有標誌這似乎不是一個尾遞歸函數？

回答

相關問題