BinaryTree的尾递归函数 [英] Tail recursive functions for BinaryTree

问题描述

我坚持实现尾递归foreach，reduce，map和toList函数，以非常简单地实现二叉树.

I am stuck with implementing tail recursive foreach, reduce, map and toList functions for a very simple implementation of binary tree.

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属性，因为如您所见，递归调用不是函数中的最后一个调用，并且我不知道如何重写它，因为一个函数中有多个调用，例如

I cant use @tailrec attribute because as you can see, recursive calls are not the last calls in a function, and I do not know how to rewrite it because there are several calls in one function, for example

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

我知道我可以对内部递归函数使用累加器，但是在多次调用的情况下应该如何使用累加器呢?

I know that I can use accumulator for inner recursive functions but how I should use it in case of several calls ?

谢谢.

已更新:

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))
}

推荐答案

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

Without tail recursion, a(/the) stack is used to keep track of calling functions. If you want to use tail recursion, you'll have to find a way to keep track of this information elsewhere. In simpler "linear" cases, such as factorial, this information is pretty limited and can often easily be taken care of by using an accumulator.

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

In your case, the problem is that the recursion isn't linear. After one recursive call, the function doesn't just compute the result, but it makes another recursive call before being able to get to the result.

在这种情况下，为了应用尾递归，您将必须明确跟踪必须进行的其余递归调用.一种简单的方法是简单地保留一个待办事项"列表.例如:

In order to apply tail recursion in this case, you will have to explicitly keep track of the remaining recursive calls that have to be made. An easy way is to simply keep a "to-do" list. For example:

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一无所知. :)

Disclaimer: I know nothing about scala. :)

这篇关于BinaryTree的尾递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！