不能寫在尾遞歸的方法在斯卡拉

Question

我有一個函數：

@tailrec 
def sampleTailRec(list: List[Int]) : List[Int] = { 
    if(list.nonEmpty) { 
    val value: Int = list.head * 2 
    List(value) ++ sampleTailRec(list.drop(1)) 
    } else { 
    List() 
    } 
} 

這是給我下面的編譯錯誤

不能優化@tailrec標註的方法sampleTailRec：它包含一個遞歸調用不是在末尾位置 列表（值）++ sampleTailRec（list.drop（1））

我曾試圖在尾編寫代碼遞歸

無法理解爲什麼我的代碼不在尾遞歸&如何使這個方法尾遞歸？

Answer 1

尾遞歸調用不會在任何後續操作中修改（或使用）遞歸調用的結果。你的例子的確如它預先列表（值）。這抑制了優化。通常你可以通過調用更多的狀態來實現尾遞歸。

Answer 2

您的方法sampleTailRec不是尾遞歸。

只有遞歸調用是方法返回之前發生的最後一件事，方法纔是遞歸的。在你的方法中情況並非如此。看這句話：

List(value) ++ sampleTailRec(list.drop(1)) 

想想當執行這條線會發生什麼：

• 首先，list.drop(1)評估
• 然後，該方法遞歸調用：sampleTailRec(list.drop(1))
• 那麼結果被附加到List(value)

請注意，在遞歸調用之後執行一個步驟 - 遞歸調用的結果用於確定最終結果。

Answer 3

如果我的理解是正確的，你正試圖以2乘以每個元素列表，看看這個：

$ scala 
Welcome to Scala version 2.10.4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_05). 
Type in expressions to have them evaluated. 
Type :help for more information. 

scala> @scala.annotation.tailrec 
    | def sampleTailRec(list: List[Int], accumulator: List[Int] = List.empty[Int]) : List[Int] = { 
    |  list match { 
    |  case Nil => accumulator.reverse 
    |  case head :: Nil => sampleTailRec(Nil, head * 2 :: accumulator) 
    |  case head :: tail => sampleTailRec(tail, head * 2 :: accumulator) 
    |  } 
    | } 
sampleTailRec: (list: List[Int], accumulator: List[Int])List[Int] 

scala> sampleTailRec(1 to 10 toList) 
warning: there were 1 feature warning(s); re-run with -feature for details 
res0: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20) 

Answer 4

您可以將方法轉換爲以下之一，它採用tail-以您打算的方式進行遞歸，並且具有相同（線性）的複雜度：

def sampleTailRec(list:List[Int]): List[Int] = { 
    @tailrec 
    def sampleTailRec_aux(l: List[Int], result: List[Int]): List[Int] = { 
    if (l.nonEmpty) sampleTailRec_aux(l.tail, (l.head * 2) :: result) 
    else result.reverse 
    } 
    sampleTailRec_aux(list, List()) 
}