Scala 中的尾递归优化 | Baeldung中文网

1. 简介

一般来说，我们可以将递归问题分为头递归和尾递归。头递归在递归深度较大时容易引发栈溢出错误（Stack Overflow）。

本篇文章将展示 Scala 是如何通过尾递归优化来解决这个问题的——它可以把调用栈压缩到仅一个栈帧，从而避免爆栈风险。

2. 计算列表长度

我们尝试分别使用头递归和尾递归来实现计算一个列表的长度。

对于一个大小为 N 的 List，计算其长度的算法可以描述为：

如果列表为空，则返回 0
如果列表不为空，则返回 1 加上其余部分（去掉第一个元素后的新列表）的长度

2.1 头递归版本

下面是头递归的实现方式：

def recursiveLength(list: List[String]): Long = list match {
    case Nil => 0
    case head :: tail => 1 + recursiveLength(tail)
}

这个实现是对上述算法的直接翻译。但问题在于：如果列表太长，递归层级过深，很容易导致栈溢出。

2.2 尾递归版本 ✅推荐

再来看尾递归的实现：

@tailrec
def tailRecursiveLength(list: List[String], accumulator: Long): Long = list match {
    case Nil => accumulator
    case head :: tail => tailRecursiveLength(tail, accumulator + 1)
}

这个版本有几个关键点值得注意：

使用了 @tailrec 注解，用于告诉编译器进行尾递归优化检查
最关键的一点是：方法的最后一个操作必须是递归调用本身

只要满足这一点，Scala 就可以将整个递归过程优化为单个栈帧，极大减少内存消耗。

2.3 编译器支持与错误提示 ⚠️

如果我们不小心写错了，比如在头递归方法上加上 @tailrec 注解，编译器会报错：

“could not optimize @tailrec annotated method recursiveLength: it contains a recursive call not in tail position”

乍一看可能不太明显为什么原来的写法不是尾递归。我们把代码稍微展开一下就清楚了：

def recursiveLengthVerbose(list: List[String]): Long = list match {
    case Nil => 0
    case head :: tail => {
        val accumulator = recursiveLengthVerbose(tail)
        1 + accumulator 
    }
}

可以看到，最后一行执行的是加法运算，而不是递归调用。所以这并不是尾递归。幸运的是，Scala 编译器能帮我们识别这种错误 ❌。

3. 总结

即使是像计算列表长度这样简单的任务，头递归也可能因为栈深度限制而失败。虽然尾递归写起来可能看起来“不够自然”，但在需要处理大量数据或深层嵌套的情况下，它是更安全、更高效的选择。

Scala 编译器对尾递归的支持做得很好，不仅能自动优化，还能提醒我们哪里写错了。合理利用这一特性，可以让我们的程序更加健壮和高效。

一如既往，文中所有代码都可以在 GitHub 上找到。

Persistence

REST

Security