如何用显式栈把递归改写成迭代？需要保存哪些状态？

简化版

递归依赖调用栈保存函数参数、局部变量和返回位置。改成迭代时，需要用显式栈保存这些状态。每个栈帧通常包含当前节点/参数、处理阶段、部分结果等信息。

详细版

递归改迭代不是简单把函数调用换成 while，关键是模拟调用栈。

需要保存：

当前处理对象，比如节点、下标、区间。
下一步执行阶段，比如还没处理子节点、左子树已处理、右子树已处理。
必要的局部变量或部分结果。
回溯时要恢复的位置。

前序遍历可以只压节点，因为访问顺序简单；后序遍历、回溯、复杂 DFS 常要压“状态帧”。面试回答要强调：显式栈保存的是递归现场。

完整版教学

一、递归调用栈到底保存了什么

每次函数调用，运行时都会创建一个栈帧。栈帧里有参数、局部变量、返回地址，以及函数执行到哪里的信息。

例如递归 DFS：

function dfs(node) {
  if (!node) return;
  visit(node);
  dfs(node.left);
  dfs(node.right);
}

当执行 dfs(node.left) 时，当前 node 和“左子树回来后还要处理右子树”这件事都被调用栈保存了。改成迭代时，如果不保存这些信息，就不知道下一步该回到哪里。

二、简单前序为什么容易改

前序遍历顺序是根、左、右。它访问节点后，不需要等子节点返回再做复杂收尾，所以可以只用节点栈。

stack.push(root);
while (stack.length) {
  const node = stack.pop();
  visit(node);
  if (node.right) stack.push(node.right);
  if (node.left) stack.push(node.left);
}

先压右再压左，是因为栈后进先出，左节点要先被弹出。这里显式栈只保存“未来要访问的节点”，不需要保存执行阶段。

三、复杂递归为什么需要状态帧

后序遍历顺序是左、右、根。访问根必须等左右都处理完，这就需要知道当前节点处于哪个阶段。

一种通用状态帧：

Frame {
  node
  state: 0/1/2
}

含义可以是：

0：准备处理左子树
1：左子树已处理，准备处理右子树
2：左右都处理完，访问自己

这就是手动模拟递归函数的执行位置。越复杂的递归，越需要把隐式状态显式化。

四、回溯算法要保存哪些状态

回溯不只保存当前位置，还要保存选择列表、当前路径、循环下标，甚至撤销动作。

例如组合搜索中，递归天然会保存 start 和当前路径。改成显式栈时，帧里至少要有：

状态	作用
当前下标	知道从哪里继续枚举
当前路径	知道已经选了什么
阶段标记	知道是进入还是回溯
部分结果	必要时保存子问题结果

如果路径很大，每个帧都复制路径会占很多内存。工程上可能需要共享结构或手动 push/pop。

五、递归改迭代的收益和代价

收益是避免系统调用栈溢出，并且可以更精细地控制执行过程，比如暂停、恢复、限时、分批处理。

代价是代码复杂度上升。递归由语言运行时帮你管理现场；迭代要自己维护栈帧，状态机写错很容易漏处理或重复处理。

递归：代码短，依赖调用栈
显式栈：代码长，可控性强

所以不是所有递归都要改。树深可控、逻辑清晰时递归很好；深度不可控或生产环境怕栈溢出时，再考虑显式栈。

六、如何验证改写正确

验证时要用浅层、深层、空输入和只有单边分支的输入。尤其是深链，比如 100000 个节点的单链式树，递归可能栈溢出，显式栈应该能正常跑。

记忆钩子：递归改迭代不是“去掉递归”四个字，而是把调用栈里的参数、局部变量和返回位置搬到自己的栈帧里。

七、常见误区与追问

误区：所有递归都能只用节点栈改写。 简单前序可以，后序、回溯和分治通常需要阶段状态。
误区：显式栈空间就是 O(1)。 它仍然要保存待处理状态，空间通常和递归深度同阶。
误区：迭代一定更快。 迭代避免函数调用开销，但状态管理更复杂，真实性能要看实现。
追问：什么时候必须改迭代？ 输入深度不可控、可能栈溢出、需要暂停恢复或限制执行步数时。
追问：状态帧里放什么？ 放递归函数恢复执行所需的一切：参数、阶段、局部变量和部分结果。

八、加强记忆

递归的本质是运行时帮你维护一摞栈帧。显式栈改写就是把这摞栈帧自己建出来。简单 DFS 只存节点，复杂 DFS 要存阶段；回溯还要存路径和选择位置。抓住“保存递归现场”这个核心，就不会把迭代改写写成玄学。

简化版

详细版