如何使用尾递归优化现有DFS算法？求实现方案

问题分析 #

原DFS函数并非尾递归形式——递归调用完成后还需执行累加操作（tmp += dfs(...)后再加当前节点值返回），这会导致每次递归调用后都要保留栈帧处理后续计算。尾递归要求函数最后一步仅调用自身，无额外后续操作，这样JavaScript引擎可优化栈空间，规避栈溢出风险。

尾递归实现方案 #

通过携带累加器参数+维护待处理节点队列实现尾递归：

• 用acc（累加器）保存当前已计算的总和
• 用数组存储待处理节点，每次取出一个节点后，将其值加入累加器，再把它的子节点倒序加入待处理数组（保证遍历顺序与原DFS一致）
• 递归函数最后一步直接调用自身，传入更新后的累加器与剩余待处理节点

实现代码 #

const tree = {
  val: 1,
  children: [
    { val: 2, children: [] },
    {
      val: 3,
      children: [
        { val: 4, children: [] },
        { val: 5, children: [] },
      ],
    },
    { val: 6, children: [] },
  ],
};

// 尾递归DFS求和函数
function tailRecursiveDfs(nodes, acc) {
  // 无待处理节点时返回累加结果
  if (nodes.length === 0) {
    return acc;
  }
  // 取出第一个待处理节点
  const [current, ...rest] = nodes;
  // 当前节点值加入累加器，子节点倒序后拼接到待处理列表（匹配原DFS遍历顺序）
  return tailRecursiveDfs([...current.children.reverse(), ...rest], acc + current.val);
}

// 初始调用：传入根节点数组与初始累加器0
const ret = tailRecursiveDfs([tree], 0);
console.log("ret: ", ret); // 输出21

代码说明 #

1. 尾递归核心：tailRecursiveDfs的最后一步仅调用自身，无任何后续计算，符合尾递归定义。
2. 遍历顺序对齐：将子节点reverse()后加入待处理列表，是为了和原DFS的先左后右遍历顺序保持一致（原代码for循环从0到末尾遍历子节点，倒序后加入数组，取出时顺序与原遍历逻辑匹配）。
3. 累加器作用：每次递归将当前节点值累加到acc，所有节点处理完成后，acc即为总和。

结果验证 #

运行代码后输出21，与原DFS函数输出完全一致，同时实现了尾递归优化。

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