已实现尾递归DFS前序时间获取，如何实现后序时间的尾递归函数式实现？

要实现函数式+尾递归的DFS后序时间记录，核心是通过显式栈模拟递归状态，并给每个节点标记「是否已处理子节点」——因为后序遍历要求必须等所有子节点处理完成后，再记录当前节点的时间戳。

核心逻辑 #

尾递归的关键是把所有待处理状态（栈、时间戳、结果集合）作为参数传递，每一步都生成新的不可变状态，避免副作用：

1. 栈中存储(节点, 访问标记)的元组：false表示未处理子节点，true表示子节点已处理完毕
2. 初始状态：栈中放入根节点（标记为未访问），时间戳从0开始，结果集合为空
3. 递归分支：
   • 弹出未访问节点：先将该节点标记为已访问重新压栈，再逆序压入所有子节点（保证子节点按原顺序处理，利用栈后进先出特性），继续递归
   • 弹出已访问节点：记录当前时间戳到该节点的后序时间，时间戳+1，继续递归
4. 栈为空时，返回最终的后序时间集合

函数式代码示例（Scala） #

import scala.annotation.tailrec

// 定义节点结构
case class Node(id: String, children: List[Node])

/**
 * 尾递归后序时间记录
 * @param stack 待处理的节点栈，元素为(节点, 是否已处理子节点)
 * @param timestamp 当前时间戳
 * @param postTimes 已记录的后序时间映射
 * @return 所有节点的后序时间Map
 */
@tailrec
def postorderTailRec(
    stack: List[(Node, Boolean)],
    timestamp: Int,
    postTimes: Map[String, Int]
): Map[String, Int] = stack match {
  // 栈空，返回结果
  case Nil => postTimes
  // 处理未访问的节点：压回已访问标记，再压入子节点
  case (node, false) :: rest =>
    val childStack = node.children.map((_, false)).reverse // 逆序压入保证子节点处理顺序
    val newStack = (node, true) :: childStack ::: rest
    postorderTailRec(newStack, timestamp, postTimes)
  // 处理已访问的节点：记录时间戳
  case (node, true) :: rest =>
    val updatedPostTimes = postTimes + (node.id -> timestamp)
    postorderTailRec(rest, timestamp + 1, updatedPostTimes)
}

// 调用示例
val root = Node("A", List(
  Node("B", List(Node("D", Nil))),
  Node("C", Nil)
))
val result = postorderTailRec(List((root, false)), 0, Map.empty)
// 输出结果：Map(D -> 0, B -> 1, C -> 2, A -> 3)

关键细节说明 #

• 不可变数据：所有状态（栈、时间戳、结果Map）都是不可变的，每一步递归都生成新的实例，符合函数式编程要求
• 尾递归优化：Scala的@tailrec注解会强制编译器将递归转换为循环，避免栈溢出问题
• 子节点逆序压栈：因为栈是后进先出结构，逆序压入子节点能保证弹出时按原顺序处理（比如节点B的子节点D，逆序后压栈还是D，弹出时先处理D）

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