Scala中元组列表尾递归归并排序@tailrec不生效问题排查

问题原因 #

你遇到的报错看似矛盾——明明给merge方法加了final注解，却仍被提示“method merge is neither private nor final”。这是因为Scala的尾递归优化对方法的确定性要求极高：仅仅标记final还不够，若方法是默认的公共可见性，编译器无法完全排除外部代码通过继承等方式干扰优化的可能，因此会拒绝进行尾递归优化。

解决方案 #

有两种方式可以满足编译器的尾递归优化要求：

方案1：将merge设为私有方法

私有方法默认无法被重写，编译器可以安全地执行尾递归优化：

def mergeSort(lst: List[(Int, Int)]): List[(Int, Int)] = {
  if (lst.length <= 1) lst
  else {
    val mid = lst.length / 2
    val left = mergeSort(lst.take(mid))
    val right = mergeSort(lst.drop(mid))
    merge(left, right)
  }
}

@tailrec
private def merge(left: List[(Int, Int)], right: List[(Int, Int)], acc: List[(Int, Int)] = Nil): List[(Int, Int)] = (left, right) match {
  case (Nil, _) => acc.reverse ::: right
  case (_, Nil) => acc.reverse ::: left
  case (h1 :: t1, h2 :: t2) =>
    if (h1._1 <= h2._1) merge(t1, right, h1 :: acc)
    else merge(left, t2, h2 :: acc)
}

方案2：使用private[this]限制方法作用域

如果需要保留方法的内部可见性（比如在同一个类的其他方法中调用），可以用private[this]标记，将方法限制为仅当前实例可调用，彻底消除被重写的可能：

@tailrec
private[this] final def merge(left: List[(Int, Int)], right: List[(Int, Int)], acc: List[(Int, Int)] = Nil): List[(Int, Int)] = (left, right) match {
  case (Nil, _) => acc.reverse ::: right
  case (_, Nil) => acc.reverse ::: left
  case (h1 :: t1, h2 :: t2) =>
    if (h1._1 <= h2._1) merge(t1, right, h1 :: acc)
    else merge(left, t2, h2 :: acc)
}

补充说明 #

你的mergeSort方法本身不是尾递归（递归调用后还需要执行merge操作），因此无需添加@tailrec注解，这部分逻辑是正确的。

内容的提问来源于stack exchange，提问作者JokerFever