尾遞迴

使用常規遞迴，每個遞迴呼叫將另一個條目推送到呼叫堆疊。遞迴完成後，應用程式必須將每個條目一直彈回。如果有很多遞迴函式呼叫，它最終會有一個巨大的堆疊。

如果在尾部位置找到遞迴呼叫，Scala 會自動刪除遞迴。可以將註釋（@tailrec）新增到遞迴函式以確保執行尾呼叫優化。如果編譯器無法優化你的遞迴，則會顯示錯誤訊息。

定期遞迴

這個例子不是尾遞迴的，因為當進行遞迴呼叫時，函式需要跟蹤呼叫返回後它需要對結果進行的乘法。

def fact(i : Int) : Int = {
   if(i <= 1) i
   else i * fact(i-1)
}

println(fact(5))

使用引數呼叫函式將產生如下所示的堆疊：

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 * 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

如果我們嘗試使用 @tailrec 註釋此示例，我們將收到以下錯誤訊息：could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

尾遞迴

在尾遞迴中，首先執行計算，然後執行遞迴呼叫，將當前步驟的結果傳遞給下一個遞迴步驟。

def fact_with_tailrec(i : Int) : Long = {
   @tailrec
   def fact_inside(i : Int, sum: Long) : Long = {
      if(i <= 1) sum
      else fact_inside(i-1,sum*i)
   }
   fact_inside(i,1)
}

println(fact_with_tailrec(5))

相反，尾遞迴階乘的堆疊跟蹤如下所示：

(fact_with_tailrec 5)
(fact_inside 5 1)
(fact_inside 4 5)
(fact_inside 3 20)
(fact_inside 2 60)
(fact_inside 1 120)

每次呼叫 fact_inside 時，只需要跟蹤相同數量的資料，因為該函式只是將它所獲得的值返回到頂部。這意味著即使呼叫 fact_with_tail 1000000，它也只需要與 fact_with_tail 3 相同的空間量。非尾遞迴呼叫不是這種情況，因此大值可能導致堆疊溢位。