尾递归==循环
你可以将任何循环表示为尾递归调用。
背景：在纯函数式编程中，每个操作都必须返回某个值。Scala中的while循环不会返回任何表达式，只有副作用（例如更新某个变量）。它仅存在于支持来自命令式背景的程序员。Scala鼓励开发人员重新考虑使用递归替换while循环，因为递归总是会返回某个值。
因此，根据Scala：递归是新的迭代。
然而，前面的语句存在一个问题：虽然“常规”递归代码更易读，但它带来了性能损失，并携带着溢出堆栈的固有风险。另一方面，尾递归代码永远不会导致堆栈溢出（至少在Scala中），并且性能与循环相同（实际上，我确信Scala将所有尾递归调用转换为普通的迭代）。
回到问题本身，坚持使用“常规”递归没有问题，除非：
递归有两种基本类型：
在头递归中，一个函数进行递归调用，然后执行一些更多的计算，可能使用递归调用的结果。在尾递归函数中，所有计算首先发生，递归调用是最后发生的事情。
这种区别的重要性并不显而易见，但却非常重要！想象一下尾递归函数。它运行。它完成了所有的计算。在其最后一个动作中，它准备好进行递归调用。此时，堆栈帧有什么用处呢？完全没有。我们不再需要本地变量，因为我们已经完成了所有的计算。我们不需要知道我们在哪个函数中，因为我们只是要重新进入同一个函数。在尾递归的情况下，Scala可以消除创建新堆栈帧的过程，并重复使用当前堆栈帧。无论递归调用多少次，堆栈都不会变得更深。这就是使Scala中的尾递归特殊的巫术。
让我们通过例子来看看。
def factorial1(n:Int):Int =
if (n == 0) 1 else n * factorial1(n -1)
def factorial2(n:Int):Int = {
def loop(acc:Int,n:Int):Int =
if (n == 0) 1 else loop(acc * n,n -1)
loop(1,n)
}
def gcd(a: Int, b: Int) = {
def loop(a: Int, b: Int): Int =
if (b == 0) a else loop(b, a%b)
loop(math.abs(a), math.abs(b))
}
def goRec(i: Int): Unit = {
if (i < 5) {
println(i)
goRec(i+1)
}
}
def goLoop(i: Int): Unit = {
var j = i
while (j < 5) {
println(j)
j += 1
}
}
def map(f: Int => Int, xs: Stream[Int]): Stream[Int] = f -> xs match {
case (_, Stream.Empty) => Stream.Empty
case (f, x #:: xs) => f(x) #:: map(f, xs)
}
scala> map(_+1, Stream.from(0).takeWhile(_<=1000000)).last
res6: Int = 1000001
List进行相同操作会导致程序崩溃。但由于Stream是惰性的，所以这不是问题。在这种情况下，您也可以编写一个尾递归函数，但通常这不容易实现。Int解决的问题，因为你的数字将变得非常大，很可能会发生溢出，那么不要转换为Long，因为在这里也很可能会发生溢出。
对于递归来说，这意味着可能存在一些情况下你会耗尽栈空间，但更可能的是，当你切换到仅基于内存的解决方案时，你会遇到内存不足的错误。更好的建议是找到一个不会表现得那么糟糕的不同算法。
一个常见的例子是遍历二叉树数据结构。对于每个节点，您可能需要同时递归左子节点和右子节点。如果您尝试递归地编写这样的函数，首先访问左节点，然后访问右节点，那么您需要维护某种辅助数据结构来跟踪所有剩余的右节点需要被访问。然而，您可以只使用堆栈来实现相同的功能，这将更具可读性。
这种情况的一个例子是 Scala 的 RedBlack 树中的 iterator 方法。
def iterator: Iterator[(A, B)] =
left.iterator ++ Iterator.single(Pair(key, value)) ++ right.iterator