如何用尾递归实现树遍历？附现有非尾递归遍历代码

好问题！要把这个前序遍历改成尾递归实现，我们得先拆解原函数的问题，再用栈模拟的方式调整结构，让递归调用成为函数的最后一步操作。

原函数的问题：为什么不是尾递归？ #

你的原recur函数里，在调用visit(n.data)之后，会遍历子节点逐个递归调用recur(c)——但递归返回后，还要继续处理下一个子节点，这意味着递归调用不是函数的最后一个操作，所以Scala编译器没法把它优化成尾递归。

改造思路：用栈模拟递归调用栈 #

尾递归要求函数的最后一步只能是调用自身，不能有后续操作。我们可以用一个栈（这里用Scala的List，因为它的头部操作效率极高）来保存待处理的节点，每次取出栈顶节点处理，再把待处理的子节点压入栈，然后递归处理这个新栈。

这里要注意：前序遍历是先处理当前节点，再按顺序处理子节点。因为栈是后进先出的，所以我们需要把子节点逆序后压入栈，这样弹出的时候才会和原遍历顺序一致。

改造后的尾递归实现 #

import scala.annotation.tailrec

case class Node(data: String, childs: Seq[Node] = Seq.empty)

def travers(root: Node, visit: String => Unit): Unit = {
  @tailrec
  def recur(nodes: List[Node]): Unit = nodes match {
    case Nil => // 栈为空，遍历结束
    case node :: rest =>
      visit(node.data)
      // 逆序子节点后加入栈，保证弹出顺序和原前序遍历一致
      recur(node.childs.reverse.toList ++ rest)
  }
  // 初始栈只包含根节点
  recur(List(root))
}

// 测试代码和原逻辑一致
val root = Node("1", Seq(Node("2", Seq(Node("3"), Node("4")))))
travers(root, s => println(s))

代码说明 #

• @tailrec注解：用来让Scala编译器验证这个函数确实是尾递归，如果不符合会直接报错，确保我们的实现是正确的。
• 栈的处理：每次取出栈顶节点node，先调用visit处理它的数据，然后把它的子节点逆序后和剩余的栈元素合并，作为新的栈传入下一次递归。逆序操作是关键，这样能保证子节点的处理顺序和原遍历完全一致。
• 尾递归优化：因为recur的最后一步就是调用自身，编译器会把它转换成循环，避免递归带来的栈溢出风险，尤其适合处理深度很大的树结构。

内容的提问来源于stack exchange，提问作者zella