递归转循环的核心是用栈模拟调用栈，保存关键状态变量；按原递归调用顺序反向入栈子任务；尾递归可直接转为while循环；需注意访问时机以匹配前/中/后序逻辑。

递归转循环的核心是用显式数据结构（通常是栈）模拟系统调用栈的行为，把函数调用的“状态”手动保存和恢复。

识别递归中的关键状态变量

每次递归调用时，真正变化的参数、局部变量就是需要压入栈的状态。比如斐波那契中是 n，二叉树遍历中是当前节点指针；如果有多个参数（如 f(a, b, depth)），就得一起存入栈元素。

• 把原递归函数的形参列表，作为栈中每个元素的字段
• 若递归中有提前返回（如 base case），对应循环中需在入栈前或出栈后判断并跳过处理
• 注意：递归中隐式的“返回地址”在转换后由循环逻辑顺序体现，无需显式存储

用栈模拟调用与返回过程

递归本质是深度优先的调用链，用栈能自然复现这个顺序。每轮循环 pop 一个任务，处理它，并按原递归调用顺序反向 push 后续任务（因为栈是后进先出）。

• 初始时将最外层调用参数入栈
• 循环体中取出栈顶，执行当前层“主体逻辑”（如计算、访问节点）
• 再按原递归中 从右到左 的调用顺序，把子调用参数入栈（例如 f(n-1) 和 f(n-2)，要先 push n-2 再 push n-1，才能让 n-1 先被处理）

尾递归可直接扁平化为 while 循环

如果递归调用是函数的最后一个动作（即尾递归），且无后续计算，就无需栈——只需更新参数并跳转回开头，等价于 while 循环。

• 把递归参数改为可变变量
• 用 while 替代 if 判断 base case
• 每次迭代末尾更新参数，模拟“递归调用自身”
• 例如阶乘尾递归 fact(n, acc) → 初始化 acc=1，循环中 acc *= n; n--

注意副作用与执行时机差异

递归中“访问节点”可能发生在进入、中间或退出时（如前/中/后序遍历），转成循环后必须明确每项操作的位置，否则行为会改变。

• 前序：出栈即处理
• 中序：需标记节点是否已展开（如用 pair<node, bool> 表示“未访问”或“已展开”）
• 后序：更复杂，常需两个栈，或记录上一次处理的节点来判断是否该访问父节点
• 简单场景下可改用“颜色标记法”：每个节点入栈三次，分别代表进入、左子处理完、右子处理完