二叉树的尾递归函数

Question

我一直坚持为非常简单的二叉树实现实现尾递归 foreach、reduce、map 和 toList 函数。

sealed trait Tree[+A]
case object EmptyTree extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

object Tree {

  def apply[A]: Tree[A] = EmptyTree
  def apply[A](value: A): Tree[A] = Node(value, EmptyTree, EmptyTree)
  def apply[A](value: A, left: Tree[A], right: Tree[A]): Tree[A] = Node(value, left, right)

  def foreach[A](tree: Tree[A], f: (A) => Unit): Unit = {
    //@tailrec
    def iter[A](tree: Tree[A], f: (A) => Unit): Unit = tree match {
      case EmptyTree =>
      case Node(v, l, r) =>
        iter(l, f)
        f(v)
        iter(r, f)
    }
    iter(tree, f)
  }

  def reduce[A](tree: Tree[A], value: A, f: (A, A) => A): A = {
    //@tailrec
    def loop(tree: Tree[A], value: A): A = tree match {
      case Node(v, l, r) => loop(l, f(loop(r, value), v))
      case EmptyTree => value
    }
    loop(tree, value)
  }

  def map[A, B](tree: Tree[A], f: A => B): Tree[B] = {
    //@tailrec
    def iter[A](tree: Tree[A], f: A => B): Tree[B] = tree match {
      case Node(v, l, r) => Node(f(v), iter(l, f), iter(r, f))
      case EmptyTree => EmptyTree
    }
    iter(tree, f)
  }

  def toList[A](t: Tree[A]): List[A] = {
    //@tailrec
    def iter[A](t: Tree[A]): List[A] = t match {
      case Node(v, l, r) => v :: iter(l) ::: iter(r)
      case EmptyTree => List.empty
    }
    iter(t)
  }
}

测试代码：

val tree = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))
Tree.foreach(tree, (x: Int) => println(x))
Tree.reduce(tree, 0, (x: Int, y: Int) => x + y)
Tree.map(tree, (x: Int) => x + 1)
Tree.toList(tree)

我不能使用@tailrec 属性，因为如您所见，递归调用不是函数中的最后一次调用，而且我不知道如何重写它，因为一个函数中有多个调用，例如

v :: iter(l) ::: iter(r)

我知道我可以将累加器用于内部递归函数，但在多次调用的情况下我应该如何使用它？

提前致谢。

已更新：

def toListRec[A](tree: Tree[A]): List[A] = {
  @tailrec
  def iter(result: List[A], todo: List[Tree[A]]): List[A] = todo match {
    case x :: tail => x match {
      case Node(v, l, r) => iter(v :: result, l :: r :: tail)
      case EmptyTree => iter(result, tail)
    }
    case Nil => result.reverse
  }
  iter(List.empty, List(tree))
}

Answer 1

没有尾递归，一个(/the) 堆栈用于跟踪调用函数。如果您想使用尾递归，则必须找到一种方法在其他地方跟踪此信息。在更简单的 "linear" 情况下，例如阶乘，此信息非常有限，通常可以使用累加器轻松处理。

在你的例子中，问题是递归不是线性的。在一次递归调用后，该函数不仅计算结果，而且在能够得到结果之前进行另一次递归调用。

为了在这种情况下应用尾递归，您必须明确跟踪必须进行的剩余递归调用。一种简单的方法是简单地保留一个 "to-do" 列表。例如：

def toList[A](t: Tree[A]): List[A] = {
  @tailrec def iter[A](todo: List[Tree[A]], r: List[A]): List[A] =
  todo match {
    case t :: rest => t match {
      case Node(v, l, r) => iter(l :: r :: rest,  v :: r)
      case EmptyTree => iter(rest, r)
    }
    case List.empty => reverse(r)
  }
  iter(List(t), List.empty)
}

免责声明：我对scala一无所知。 :)

Answer 2

mweerden 建议的解决方案可行，但是，还有另一种解决问题的方法，我认为这种方法更优雅。这是遍历树以列出

的代码

def toList[T](t: Tree[T]): List[T] = {
  def tailRecursive(tree: Tree[T], acc: List[T]): List[T] = tree match {
    case EmptyTree => acc
    case Node(value, right, left) => 
      tailRecursive(left, value :: tailRecursive(right, acc))
  }
  tailRecursive(t, List())
}

解法暗示该树为二叉搜索树，产生的列表会按升序排列（如果不需要升序，第6行可以改，把值放在第一次递归调用的前面或者直接进入蓄能器是可能的）。

二叉树的尾递归函数

Tail recursive functions for BinaryTree

scala

functional-programming

tail-recursion