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 注释，当尾递归优化不可用时发出错误。