如何用尾递归实现Scala表达式ADT的求值函数？

我定义了如下用于表示表达式的ADT：

trait Expression {
  def value: Int
}

case class Number(value: Int) extends Expression
case class Add(a: Expression, b: Expression) extends Expression {
  override def value: Int = a.value + b.value
}

还可以添加减法、乘法等操作的case class。例如，表达式"2 + 7 + 9"可以表示为：

val addingThreeNumbers = Add(Number(2), Add(Number(7), Number(9)))

我实现了如下求值函数，它可以正常工作，但想知道如何用尾递归实现：

def evaluate(e: Expression): Int = {
  e match {
    case Number(value) => value
    case Add(a, b)     => evaluate(a) + evaluate(b)
  }
}

尾递归实现方案 #

普通递归的问题在于，evaluate(a) + evaluate(b)这种写法里，调用完evaluate(a)之后，还得等着evaluate(b)的结果出来才能做加法运算——这不符合尾调用的要求（尾调用是指递归调用是函数的最后一步操作，没有后续计算）。要改成尾递归，核心思路是用累加器记录当前已计算的总和，同时用一个列表模拟栈来保存待处理的表达式，每次递归只处理栈顶元素，且递归调用是函数的最后一步。

下面是具体的Scala实现：

import scala.annotation.tailrec

def evaluateTailRec(e: Expression): Int = {
  @tailrec
  def loop(acc: Int, remaining: List[Expression]): Int = remaining match {
    case Nil => acc
    case expr :: rest => expr match {
      case Number(n) => loop(acc + n, rest)
      case Add(a, b) => loop(acc, a :: b :: rest) // 栈是后进先出，先处理a再处理b，和原逻辑一致
    }
  }

  loop(0, List(e))
}

逻辑说明 #

1. 辅助函数loop加上@tailrec注解，让编译器确认这是尾递归并进行优化（避免栈溢出）。
2. acc用来存当前已经累加的结果，remaining是待处理的表达式列表（模拟栈结构）。
3. 初始调用时，累加器从0开始，把要计算的表达式放到待处理列表里：loop(0, List(e))。
4. 处理每个待处理表达式：
   • 如果是Number(n)，直接把n加到累加器里，继续处理剩下的表达式。
   • 如果是Add(a, b)，把a和b依次加入待处理列表——因为列表是后进先出，这样会先处理a再处理b，和原递归的计算顺序完全一致。
5. 当待处理列表为空时，累加器里的数值就是最终结果。

测试用例 #

用你给出的示例测试：

evaluateTailRec(addingThreeNumbers) // 结果为18，和原函数输出一致

这种方式很容易扩展到减法、乘法等其他运算。比如要支持减法，只需要新增Subtract(a, b)的case class，然后在loop的match分支里添加对应的处理逻辑——比如把Subtract(a, b)转换成a :: Negate(b) :: rest（需要新增Negate这个表示取反的case class），或者直接调整累加规则，具体看你需要的语义。

内容的提问来源于stack exchange，提问作者M.G.