scala – BinaryTree的尾递归函数

发布时间：2020-12-16 18:06:20 所属栏目：安全来源：网络整理

导读：我坚持实现tail递归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

我坚持实现tail递归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,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,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,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,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,(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,r) => iter(v :: result,l :: r :: tail)
      case EmptyTree => iter(result,tail)
    }
    case Nil => result.reverse
  }
  iter(List.empty,List(tree))
}

解决方法

没有尾递归,(/)栈用于跟踪调用函数.如果你想使用尾递归,你必须找到一种在其他地方跟踪这些信息的方法.在更简单的“线性”情况下,例如阶乘,这种信息非常有限,并且通常可以通过使用累加器来轻松处理.

在您的情况下,问题是递归不是线性的.在一次递归调用之后,该函数不仅计算结果,而且在能够获得结果之前进行另一次递归调用.

为了在这种情况下应用尾递归,您必须明确地跟踪必须进行的剩余递归调用.一种简单的方法是简单地保留“待办事项”列表.例如：

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,r) => iter(l :: r :: rest,v :: r)
      case EmptyTree => iter(rest,r)
    }
    case List.empty => reverse(r)
  }
  iter(List(t),List.empty)
}

免责声明：我对scala一无所知.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!