递归转循环的关键是模拟调用栈，显式保存状态（参数、局部变量、返回位置）；需识别递归结构、提取状态变量，并用栈管理执行流程，尾递归可简化为变量更新循环。

递归转循环不是简单地把函数调用换成 while，关键在于模拟递归的“调用栈”行为——把每次递归需要的状态（参数、局部变量、返回位置）显式存到栈里，再用循环逐步处理。

识别递归结构，提取状态变量

先看一个典型例子：计算二叉树节点数的递归写法：

def count_nodes(root):
  if not root: return 0
  return 1 + count_nodes(root.left) + count_nodes(root.right)

这个递归有三个隐含状态：当前节点（root）、左子树结果、右子树结果。但循环无法直接“等待”左右结果返回，所以得把“待处理节点”和“该节点的计算上下文”分开保存。最简方式是只压入节点，然后边遍历边累加；更通用的方式（尤其涉及返回值组合时）要记录“处理阶段”，比如：
• 阶段 0：刚访问节点，需先处理左子树
• 阶段 1：左子树已处理完，接下来处理右子树
• 阶段 2：左右都完成，可合并结果

用栈模拟调用栈，手动管理执行流程

递归靠系统栈自动保存现场，循环得自己建栈来存：
• 栈元素通常是元组或字典，例如 (node, stage, left_result, right_result)
• 每次循环 pop 一个任务，根据 stage 决定下一步：
　　– stage == 0：若 node 存在，push (node, 1, ?, ?)，再 push (node.left, 0, ?, ?)
　　– stage == 1：push (node, 2, left_result, ?)，再 push (node.right, 0, ?, ?)
　　– stage == 2：算出 total = 1 + left_result + right_result，作为当前节点结果返回给上层（即赋值给父任务的对应字段）

注意：返回值不是直接 return，而是存回栈中对应父任务的字段，靠栈的 LIFO 特性保证顺序。

简化场景：尾递归可直接转 for/while

如果递归只在最后一步调用自身（如阶乘、链表遍历），没有“调用后还要做别的事”，就属于尾递归，转换最简单：
• 把参数变成循环变量
• 把递归调用替换成更新变量 + continue

# 尾递归版本
def factorial(n, acc=1):
  if n   return factorial(n-1, n*acc)

# 对应循环
def factorial_iter(n):
  acc = 1
  while n > 1:
    acc *= n
    n -= 1
  return acc

调试技巧：打印栈状态，对齐递归步骤

刚开始重构时容易漏状态或错顺序。建议在循环体开头打印栈内容，对照原递归的调用/返回序列：
• 原递归每进入一层，对应 push 一次
• 每 return 一次，对应 pop 一次并更新上层状态
• 当栈为空且无新任务入栈，过程结束

常见坑：
• 忘记初始化栈（空输入也要考虑）
• 多次 push 同一节点导致重复处理
• stage 转换逻辑写反（比如该进 stage 1 却进了 stage 2）
• 结果合并时用了错误的中间变量名