递归转迭代的核心是将隐式调用栈显式化，需用Frame封装参数、中间变量和stage阶段标识，按逆序压栈并分阶段还原执行流，确保上下文可控且具备深度防护机制。

递归转迭代的核心不是去掉递归逻辑，而是把隐式调用栈显式化。关键在于：每次函数调用时压入的局部变量、参数、执行位置（即“回到哪一行继续”），都得用一个结构体或对象封装好，存进你自己维护的栈里。

用 Frame 封装每层调用状态

不要只存节点或数值，要存完整上下文。一个典型的 Frame 至少包含：

• 当前参数值（如 node、index、n 等变化量）
• 局部计算中间量（比如递归中先算 leftResult，再算 rightResult，这些变量得保留在 Frame 中）
• 阶段标识（stage / location），用于区分“刚进入”“刚从左子调用返回”“刚从右子调用返回”
• 可选：返回地址模拟——多数场景可用 stage 替代，比如 stage=0 表示执行前序逻辑，stage=1 表示该处理左子，stage=2 表示该处理右子，stage=3 表示收尾

分阶段还原执行流，避免顺序错乱

递归天然有执行顺序（如 DFS 先访问自己 → 左 → 右），迭代中必须靠入栈顺序 + stage 控制来复现。常见技巧：

• 想模拟“先访问自己，再递归左，最后递归右”，就把 右子任务、左子任务、自身处理任务 按此逆序压栈（后序执行的先压）
• 若某一层需要等两个子结果再计算（如树的高度、表达式求值），就用 stage 标记“已处理左”“等待右”“左右都齐了”，并在弹出时根据 stage 决定下一步动作
• 遇到需要暂存中间结果的场景（如 fib(n-1)+fib(n-2)），Frame 中必须带字段如 leftVal、rightVal，并在 stage 跳转时更新它们

树类问题的通用三段式模板

以任意二叉树遍历+计算类递归为例，可统一建模为三个阶段：

• Stage 0（进入）：记录当前节点，初始化中间变量（如 sum=0, height=0），然后压入“处理左子”的 Frame（stage=1）
• Stage 1（左回）：取出左子返回值，存入当前 Frame 的 leftRes 字段，再压入“处理右子”的 Frame（stage=2）
• Stage 2（右回）：取出右子返回值，填入 rightRes，执行合并逻辑（如 return leftRes + rightRes + node.val），作为本层返回值传给上层

这样每一层的变量生命周期、依赖关系、控制流向都完全可控，深层嵌套也不会丢失上下文。

不依赖语言特性的安全边界设计

JavaScript 不支持尾调用优化，C/C++ 无统一栈大小保障，所以不能假设深度上限。建议在栈操作中加入：

• 深度计数器：每个 Frame 带 depth 字段，循环中检测是否超限（如 >10000），及时报错或降级
• 异步切片开关：对超深结构（如用户上传的嵌套 JSON），每处理 N 个 Frame 后用 queueMicrotask 让出主线程，避免卡死 UI
• 栈容量预估：初始栈 size 可设为 maxDepth × avgFrameSize，避免频繁数组扩容影响性能