Scala的二叉树尾和递归

Question

所以我有下面的代码来定义一个二进制树。

sealed abstract class BinTree {
  def sum = sumAcc(0)
  def sumAcc(acc: Int): Int
}
case class NonEmpty(val elem: Int, val left: BinTree, val right: BinTree) extends BinTree {
  def sumAcc(acc: Int) = right.sumAcc(left.sumAcc(elem + acc))
}
case object Empty extends BinTree {
  def sumAcc(acc: Int) = acc
}
val rootTree = NonEmpty(1, NonEmpty(2, NonEmpty(3, Empty, Empty), Empty), Empty)
rootTree.sum

sum方法尾部是递归的吗？。我怀疑它不是尾递归的，因为对right.sumAcc的调用必须等待对left.sumAcc(elem + acc)的调用才能终止。

如果它不是尾部递归的，我该如何更改它？

Answer 1

好的，所以使用注释中指出的解决方案，我将答案重写为尾部递归。我在一个helper方法中使用了一个累加器和一个隐式堆栈。通过注释，我们可以检查该方法实际上是尾部递归的。

这是新代码，以防有人发现它有帮助。

import scala.annotation.tailrec
sealed abstract class BinTree
case object Empty extends BinTree
case class NonEmpty(val elem: Int, val left: BinTree, val right: BinTree) extends BinTree
val rootTree = NonEmpty(1, NonEmpty(2, NonEmpty(3, Empty, Empty), Empty), Empty)
def sumTailRec(bt: BinTree) = {
  @tailrec
  def sumAccStack(trees: List[BinTree], acc: Int): Int = trees match {
    case Nil => acc
    case Empty :: rs => sumAccStack(rs, acc)
    case NonEmpty(e, l, r) :: rs => sumAccStack(l :: r :: rs, e + acc)
  }
  sumAccStack(List(bt), 0)
}
sumTailRec(rootTree)

Answer 2

在您的情况下，函数不是尾递归的，但原因有点不同——没有等待，程序按顺序执行，left.sumAcc在right.sumAcc之前求值，但这仍然是一个问题，因为left.sumAcc调用是回避的，但不在尾位置。即使你想删除它，你的解决方案也有其他问题。

要检查尾递归是否可以应用于函数，可以使用@tailrec注释。在您的情况下，编译器错误消息将是：

错误：（11，7）无法优化@tailrec注释的方法sumAcc：它既不是私有的，也不是最终的，因此可以重写

def sumAcc（acc:Int）=右.sumAcc（左.sumAck（elem+acc））

为什么会发生这种情况，请参阅为什么Scala编译器不应用尾调用优化，除非方法是最终方法？问题：

除非一个方法被标记为final，否则在进行递归调用时可能不会调用自己。

如果您尝试将final添加到NonEmpty sumAcc，编译器也会告诉您这一点。错误消息将更改为：

错误：（11，38）无法优化@tailrec注释的方法sumAcc：它包含一个针对超类型NonEmpty.this.right.type 的递归调用

最终定义sumAcc（acc:Int）=右.sumAcc（左.sumAck（elem+acc））

Millie Smith在评论中链接的解决方案克服了这一点，因为它不使用重写来实现函数，而是使用模式匹配（即函数中的类型检查），因此一个函数处理Leaf和Node类型的遍历，并且该函数的结构使得在每种情况下只对sumAcc进行一次调用。