避免for循环达到scala中的尾递归状态

Question

我已经编写了以下方法来打印任意元数树结构。（深度优先搜索）

def treeString[A](tree: Tree[A]): String = {

  def DFS(t: Tree[A], acc: String = "", visited: List[String] = Nil, toClose: Int = 0): String = t match {
    case Leaf(id, terminal) if !visited.contains(id) => {
      acc + " " + terminal.name + "[" + id.toString + "] " + ")"*toClose
    }
    case Node(id, op, args @_*) if !visited.contains(id) => {
      var state = acc + " " + op.name + "[" + id.toString + "] " + "("
      var args_visited: List[String] = List(id)
      for (i <- args.tail) {
        state = DFS(i, state , visited ::: args_visited) + " , "
        args_visited = args_visited ++ List(i.id)
      }
      DFS(args.head, state , visited ++ args_visited, toClose + 1)
    }
    case _ => acc
  }
  DFS(tree)
}

scala 编译器声称此函数不是 tail recursive。但是在尾部位置我有正确的 DFS(..) 调用。循环中进行的所有 DFS(..) 调用都将以迭代方式完成，因此堆栈安全。

我知道如果树无限深就会发生堆栈溢出。我们有处理这些情况的技术吗？

Answer 1

我必须同意@VictorMoroz。问题是你的声明：

state = DFS(i, state , visited ::: args_visited) + " , "

不在尾部位置。它确实创建了一个新堆栈，因此，您的方法不再是尾递归了。

无需深入研究您的数据结构，这里介绍以 DFS 方式尾递归遍历树的方法。

sealed trait Tree[+A]
  case class Leaf[A](value: A) extends Tree[A]
  case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A]
  case class Element(id:Int, name:String)


  def DFS[T](t:Tree[T]): List[Element] = {
    @tailrec
    def _dfs(rest:List[Tree[T]], visited:List[Element]):List[Element] = {
      rest match {
        case Leaf(v:Element) =>  v :: visited  

        case Node(l,r) :: rs => _dfs(l::r::rs,visited)

      }
    }
    _dfs(List(t),Nil)
  }

关键是使用显式堆栈 - 这里以列表的形式。

I understand that if the tree is infinitely deep a stack overflow will occur.

这是正确的。基本上，在大多数编程语言中，每个方法调用都会保留一些堆栈内存。简单来说，尾递归允许编译器忽略之前的状态——不需要之前的堆栈。

请记住，DFS 无法确保找到 global optima，如果应该满足则不应使用。

后记： @tailrec 注释是对编译器的友好提示，用于在编译时检查您的方法是否可以优化（Scala 默认执行尾调用优化）。

Answer 2

我成功地达到了尾递归状态。

尽管代码很优雅，但我确实质疑函数式方法的 cost/benefit。大多数时候，如何通过算法手动传递堆栈并不明显。

无论如何，这里真正的问题在于 JVM 的递归问题，scala 编译器仍然试图为我们提供尾递归特性的逃避，但让事情正常运行通常是一场噩梦

def treeString[A](tree: Tree[A]): String = {

  def dropWhile[A](l: List[A], f: A => Boolean): List[A] =
    l match {
      case h :: t if f(h) => dropWhile(t, f)
      case _ => l
    }

  @tailrec
  def DFS(toVisit: List[Tree[A]], visited: List[String] = Nil, acc: String = "", n_args: List[Int] = Nil): String = toVisit match {
    case Leaf(id, terminal) :: tail if !visited.contains(id) => {
      val n_args_filtered = dropWhile[Int](n_args, x => x == 1)
      val acc_to_pass = acc + " " + terminal.name + "[" + id.toString + "] " + ")" * (n_args.length - n_args_filtered.length) + "," * {if (n_args_filtered.length > 0) 1 else 0}
      val n_args_to_pass = {if (n_args_filtered.length > 0 )List(n_args_filtered.head - 1) ::: n_args_filtered.tail else Nil}

      DFS(toVisit.tail, visited ::: List(id), acc_to_pass, n_args_to_pass)
    }
    case Node(id, op, args @_*) :: tail if !visited.contains(id) => {
      DFS(args.toList ::: toVisit.tail, visited ::: List(id), acc + " " + op.name + " (", List(args.length ) ::: n_args)
    }
    case Nil => acc
  }
  DFS(List(tree))
}

避免for循环达到scala中的尾递归状态

avoiding a for loop to reach a tail recursive state in scala

tree

scala

tail-recursion

tree-traversal

graph-traversal