累加器模式
在递归过程中传递状态。
累加器模式 是 CoddyKit 上的免费 Scala for Backend Engineering & Functional Programming 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Scala for Backend Engineering & Functional Programming 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Scala for Backend Engineering & Functional Programming 课程共包含 4 节课。
为什么使用累加器
普通递归会在递归调用返回后，沿着调用栈向上返回的过程中构建结果。
累加器则会将当前结果带入每次调用中，因此到达基本情况时，答案已经准备就绪。
这一小步改变可以实现尾递归，并使栈空间保持恒定。
辅助函数
累加器模式使用一个内部辅助函数，并为它增加一个参数：目前为止的结果。
外部函数只需使用一个初始值启动它，通常是 0 或空列表。
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}运行累加器
这里的完整程序使用累加器计算列表总和。
请注意，基本情况直接返回 acc，而不是返回 0。我们在沿着列表向下处理时，已经逐步构建出了总和。
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}
@main def run(): Unit =
println(sum(List(1, 2, 3, 4))) // 10比较两种结构
在普通递归中，组合步骤（h + ...）必须等待内部调用完成。
在累加器版本中，组合操作发生在调用之前，而调用是函数执行的最后一件事。
正是这种最后调用的特性，使它成为尾递归。
// Plain: combine after the call
case h :: t => h + sum(t)
// Accumulator: combine before the call
case h :: t => loop(t, acc + h)尾递归
尾递归调用是指递归调用作为函数的最后一个操作，调用之后没有其他事情需要执行。
Scala 可以将其优化为循环，重复使用同一个栈帧，因此无论递归多深，都不会发生栈溢出。
import scala.annotation.tailrec
@tailrec
def countDown(n: Int): Unit =
if (n < 0) ()
else { println(n); countDown(n - 1) }@tailrec 注解
添加 @tailrec 后，您可以要求编译器验证该函数确实是尾递归。
如果不是，编译就会失败，并显示清晰的错误信息。这样便可将隐蔽的性能陷阱转化为构建时保证。
import scala.annotation.tailrec
def sum(xs: List[Int]): Int = {
@tailrec
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}
@main def run(): Unit = println(sum((1 to 100000).toList))累加构建列表
累加器不一定只能保存数字，也可以构建集合。
这个 reverse 函数会将每个头部添加到累加器前端，从而自然地颠倒顺序。使用 :: 添加到前端速度很快，因此这种方式效率很高。
def reverse[A](xs: List[A]): List[A] = {
def loop(rest: List[A], acc: List[A]): List[A] = rest match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}实际使用 reverse
累加器从空值开始，并随着我们消耗输入而逐渐增长。
由于每个头部都会被放到 acc 的前端，第一个元素最终会位于末尾，从而在恒定栈开销下得到反转后的列表。
def reverse[A](xs: List[A]): List[A] = {
def loop(rest: List[A], acc: List[A]): List[A] = rest match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}
@main def run(): Unit =
println(reverse(List(1, 2, 3))) // List(3, 2, 1)多个累加器
辅助函数可以同时携带多个累加器。
这里我们在同一个循环中跟踪当前乘积和计数，并将两者作为元组返回。
每个累加器都会将更新后的值传递给下一次调用。
def stats(xs: List[Int]): (Int, Int) = {
def loop(rest: List[Int], prod: Int, count: Int): (Int, Int) =
rest match {
case Nil => (prod, count)
case h :: t => loop(t, prod * h, count + 1)
}
loop(xs, 1, 0)
}选择初始值
累加器的初始值必须是所执行运算的单位元。
加法使用 0，乘法使用 1，构建列表使用 Nil，连接字符串使用空字符串。
错误的初始值可能会悄无声息地产生错误答案。
// addition -> seed 0
// product -> seed 1
// list -> seed Nil
// string -> seed ""结果的顺序
累加器递归会从左到右处理元素，但基于前置添加的累加器会将元素反转。
如果构建列表时需要保留顺序，可以在最后执行 reverse，或使用追加操作，不过追加速度较慢。先前置添加、最后反转是通常采用的写法。
def mapInc(xs: List[Int]): List[Int] = {
def loop(rest: List[Int], acc: List[Int]): List[Int] = rest match {
case Nil => acc.reverse
case h :: t => loop(t, (h + 1) :: acc)
}
loop(xs, Nil)
}快速检查
选择关于累加器递归的准确说法。
回顾
累加器会将当前结果沿着递归调用向下传递，因此基本情况可以直接返回它。
这会使递归调用处于尾部位置，从而启用 Scala 的尾调用优化和 @tailrec 安全检查。
使用运算的单位元作为累加器初始值；当顺序很重要时，请在最后反转结果。
常见问题解答
「累加器模式」课时是免费的吗？
是的 — 「累加器模式」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 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 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「累加器模式」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Scala for Backend Engineering & Functional Programming 课中编写并运行代码吗？
能。每节 Scala for Backend Engineering & Functional Programming 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。