累加器模式
转换为尾递归
累加器模式 是 CoddyKit 上的免费 Scala for Backend Engineering & Functional Programming 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Scala for Backend Engineering & Functional Programming 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Scala for Backend Engineering & Functional Programming 课程共包含 4 节课。
累加器模式
累加器模式可以将非尾递归函数转换为尾递归函数。您可以通过额外的参数携带部分结果（即累加器），而不是等调用返回后再逐步构建结果。
核心思路
不要使用 n + sum(n-1)（调用后再处理），而是在调用前计算新的部分总和：sum(n-1, acc + n)。这样，递归调用就成了最后一个动作。
之前：非尾递归求和
这个直接版本不是尾递归的：加法必须等待递归调用完成。
object Main {
def sum(n: Int): Int =
if (n == 0) 0 else n + sum(n - 1)
def main(args: Array[String]): Unit = {
println(sum(50))
}
}之后：使用累加器的尾递归求和
添加一个保存当前总和的 acc 参数。递归调用现在处于尾部位置，可以进行优化。
import scala.annotation.tailrec
object Main {
@tailrec
def sum(n: Int, acc: Int = 0): Int =
if (n == 0) acc else sum(n - 1, acc + n)
def main(args: Array[String]): Unit = {
println(sum(50))
}
}尾递归阶乘
对阶乘应用相同的转换：在递归之前将乘法结果累积到累加器中。
import scala.annotation.tailrec
object Main {
@tailrec
def factorial(n: Int, acc: Long = 1): Long =
if (n <= 1) acc else factorial(n - 1, acc * n)
def main(args: Array[String]): Unit = {
println(factorial(10))
}
}隐藏累加器
额外参数属于实现细节。将尾递归工作函数包装在一个简洁的公共函数中，这样调用者就不需要看到 acc。
import scala.annotation.tailrec
object Main {
def factorial(n: Int): Long = {
@tailrec
def loop(m: Int, acc: Long): Long =
if (m <= 1) acc else loop(m - 1, acc * m)
loop(n, 1)
}
def main(args: Array[String]): Unit = {
println(factorial(6))
}
}累积构建列表
这种模式也可以构建集合。尾递归反转会将每个头部元素添加到累加器列表的前端。
import scala.annotation.tailrec
object Main {
def reverse[A](xs: List[A]): List[A] = {
@tailrec
def loop(rem: List[A], acc: List[A]): List[A] = rem match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}
def main(args: Array[String]): Unit = {
println(reverse(List(1, 2, 3, 4)))
}
}累积顺序
请注意，将元素添加到累加器前端会自然地反转顺序。对于需要保持顺序的列表构建函数，您通常会先构建反向列表，最后再反转，或者使用高效的追加结构。
尾递归 map
使用累加器构建结果列表，最后统一反转一次以恢复顺序。
import scala.annotation.tailrec
object Main {
def mapTail[A, B](xs: List[A])(f: A => B): List[B] = {
@tailrec
def loop(rem: List[A], acc: List[B]): List[B] = rem match {
case Nil => acc.reverse
case h :: t => loop(t, f(h) :: acc)
}
loop(xs, Nil)
}
def main(args: Array[String]): Unit = {
println(mapTail(List(1, 2, 3))(_ * 10))
}
}与 foldLeft 的关系
累加器模式正是 foldLeft 所概括的内容：它以尾递归方式让累加器贯穿集合。许多手动编写的累加器函数都可以改写为一次 foldLeft。
@main def run(): Unit = {
val total = List(1, 2, 3, 4).foldLeft(0)(_ + _)
println(total)
}何时使用
当递归函数处理大型线性结构、否则可能导致栈溢出时，可以使用累加器模式。它用稍微不那么直观的结构，换来了有保证的栈安全性。
快速检查
检验您对累加器模式的掌握程度。
回顾
您学习了累加器模式：
- 通过额外参数携带部分结果。
- 在递归之前计算结果，使调用处于尾部位置。
- 将累加器隐藏在简洁的公共函数之后。
- 它可以推广为
foldLeft。
常见问题解答
「累加器模式」课时是免费的吗？
是的 — 「累加器模式」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Scala for Backend Engineering & Functional Programming 课程的其余内容，请升级到 CoddyKit PRO。 Scala for Backend Engineering & Functional Programming 课程共包含 4 节课。
「累加器模式」这节课中我会学到什么？
转换为尾递归 你通过在浏览器中直接运行的动手代码来练习 Scala for Backend Engineering & Functional Programming，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Scala for Backend Engineering & Functional Programming 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Scala for Backend Engineering & Functional Programming 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「累加器模式」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Scala for Backend Engineering & Functional Programming 课中编写并运行代码吗？
能。每节 Scala for Backend Engineering & Functional Programming 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 递归基础
- tailrec 注解
- 累加器模式
- 蹦床调用