Scala/遞迴
遞迴指的是一種通用的方法，它涉及用自身來定義解或物件。遞迴函式指的是一種函式，其中函式的定義包含對函式本身的呼叫。通常，遞迴函式接受一些輸入，將其劃分為更小的部分，解決更小（可能更容易）的部分，並將它們組合起來以產生解。
遞迴函式有時可能難以理解，但具有相當大的表達能力。它們通常透過使用高階函式間接使用，或用於遞迴定義的結構，例如抽象語法樹和解析樹.
一個簡單的遞迴函式示例
def recursiveFunc(n:Int):Unit = {
if (n > 0) {
print(n + ", ")
recursiveFunc(n-1)
}
else {
println(n + ".")
}
}
recursiveFunc(4) //Prints "4, 3, 2, 1, 0.".
程式碼定義了一個名為“recursiveFunc”的函式。它是遞迴的，因為它在第四行呼叫自身。該函式的工作原理是取其引數，並測試條件“n > 0”是否為真。如果它更大，則列印該數字，並再次呼叫自身，並將該數字減去 1。如果它不大於 0，則列印該數字，並停止。請注意，返回值型別顯式註釋為“Unit”，對於遞迴函式來說，這始終是必要的。
在最後一行，函式被呼叫，引數為 4。該函式測試條件“n > 0”，由於“n”為 4，因此該條件為真。因此，它列印該數字，後跟一個逗號和空格，並再次呼叫自身，值為“n-1”。由於“n”為 4，“n-1”給出 3，因此“recursiveFunc”被呼叫，引數為 3。再次測試該條件，它仍然為真，並列印 3，之後該函式再次被呼叫，這次引數為 2。這對 2 和 1 重複進行，直到最終引數變為 0。此時，該條件不成立，唯一發生的事情是列印 0，後跟一個句號。因此，該函式列印“4, 3, 2, 1, 0.”。
遞迴函式的另一個示例是階乘函式的實現
def fact(n:Int):Int = {
if (n == 0) 1
else n*fact(n-1)
}
println(fact(5)) //Prints "120".
“fact”函式以整數“n”為引數，返回該整數的階乘，假設“n”非負。如果 n 為負，則該函式將永遠迴圈或導致堆疊溢位。
一個數字“n”的階乘定義為從 1 到“n”的整數的乘積（包括 1 和“n”）。“fact”函式正確地計算非負數的階乘。為了理解為什麼這是正確的，請考慮以下非正式論證。
如果“n”為 0，則階乘函式被定義為 1，由於“n == 0”為真，因此 if-then-else 表示式的第一個分支被執行，給出正確解 1。
如果“n”大於 0，我們首先透過呼叫“fact(n-1)”來計算數字“n-1”的階乘。假設“fact(n-1)”的計算是正確的，其結果將等於“n-1”的階乘，即從 1 到“n-1”的數字的乘積（包括 1 和“n-1”）。但是，我們想要的是“n”的階乘，即從 1 到“n”的數字的乘積（包括 1 和“n”）。然而，從 1 到“n-1”的數字的乘積乘以數字“n”，與從 1 到“n”的數字的乘積完全相同。因此，鑑於我們有從 1 到“n-1”的數字的乘積，以及數字“n”，我們可以透過將“n”乘以“fact(n-1)”來獲得“n”的階乘。因此，如果“fact(n-1)”計算正確，那麼“fact(n)”也是正確的。但是，由於我們可以任意選擇“n”，我們只需要確定“fact”是否為一個值（或基本情況）正確計算，以證明“fact”是否對所有大於該基本情況的值正確計算。由於我們已經證明階乘由“fact”對於 0 正確計算，我們可以選擇 0 作為我們的基本情況。因此，函式“fact”正確地計算了任何大於或等於 0 的數字的階乘。
間接使用遞迴來計算階乘的替代方法和更容易方法的示例
def fact2(n:Int) = (1 to n).foldLeft(1)(_*_)
def fact3(n:Int) = (1 to n).product
println(fact2(5)) //Prints "120".
println(fact3(5)) //Prints "120".
上面的示例使用了範圍、集合、高階函式和函式字面量等概念。使用間接使用遞迴的函式和方法通常是直接使用遞迴的替代方法。
相互遞迴指的是用彼此來定義的函式
//WARNING: Calling these functions will result in infinite execution or stack overflow.
def f1(a:Int) = f2(a)
def f2(a:Int) = f3(a)
def f3(a:Int):Int = f1(a)
在上面的示例中，定義了三個函式，它們相互遞迴：“f1”呼叫“f2”，“f2”呼叫“f3”，“f3”呼叫“f1”。在這樣的相互遞迴中，至少一個函式必須具有註釋的返回值型別，在本例中已選擇為“f3”。
Scala 支援尾遞迴呼叫最佳化。
def fact(n: Int, acc: Int): Int = n match {
case 0 => acc
case _ => fact(n - 1, n * acc)
}
fact(10, 1)
在scala.annotation.tailrec 中使用@tailrec 註釋，當尾遞迴最佳化不可用時發出錯誤。