BinaryTree的尾递归函数

本文介绍了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. :)