递归需优化因其简洁但易栈溢出、性能差；尾递归和单路递归可转循环，通用三步法为提取状态、栈模拟调用栈、手动展开递归体。
递归为什么需要优化
递归写起来简洁直观，尤其适合树形结构、分治问题（比如快速排序、斐波那契、汉诺塔）。但Python默认递归深度限制约1000层，且每次调用都压栈，开销大、易爆栈、难调试。实际工程中，深度稍大的递归（如遍历万级节点的树）很容易报 RecursionError 或显著拖慢性能。
识别可转循环的递归模式
不是所有递归都适合改循环，重点盯住这两类：
-
尾递归：递归调用是函数最后一步，且不依赖当前栈帧的其他变量（如
return fib(n-1) + fib(n-2)不是尾递归，return fib_tail(n-1, a+b, a)是） - 单路递归 + 显式状态：每次只递归一次，且参数能完全描述当前“位置”和“中间结果”，比如遍历链表、DFS 路径搜索、求阶乘
这类递归本质上是在模拟栈行为，完全可以手动用列表或 deque 管理状态。
递归转循环的通用三步法
以经典 DFS 遍历二叉树为例（前序）：
立即学习“Python免费学习笔记（深入）”；
-
第一步：提取状态变量 —— 原递归中变的是什么？这里是当前节点
node；是否还需要额外信息？比如路径和、深度等，一并记为元组或字典 -
第二步：用栈模拟调用栈 —— 初始化栈
stack = [root]；循环条件while stack: -
第三步：手动展开“递归体” —— 每次
pop()一个节点，处理它；再把子节点按“递归调用顺序”反向压栈（前序需先压右后压左，保证左先出）
关键点：压栈顺序必须和原递归调用顺序相反，否则执行顺序会错乱。
实战对比：斐波那契从递归到迭代
原始低效递归（指数时间）：
def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)
→ 改尾递归（仍受限于栈深度）：
def fib_tail(n, a=0, b=1): return a if n == 0 else fib_tail(n-1, b, a+b)
→ 彻底去递归，用变量滚动更新（O(1)空间，O(n)时间）：
def fib_iter(n):<br> a, b = 0, 1<br> for _ in range(n):<br> a, b = b, a + b<br> return a
这种“状态压缩”是尾递归优化的核心思想——不用存历史，只留必要变量。
复杂场景：带回溯的DFS如何转循环
比如求所有根到叶路径，原递归会维护一个 path 列表，进入时 append，退出时 pop（回溯）。转循环时不能只存节点，得连同当前路径一起入栈：
stack = [(root, [root.val])]<br>while stack:<br> node, path = stack.pop()<br> if not node.left and not node.right:<br> result.append(path)<br> if node.right:<br> stack.append((node.right, path + [node.right.val]))<br> if node.left:<br> stack.append((node.left, path + [node.left.val]))
注意：path + [...] 创建新列表，避免共享引用；若追求效率，也可存 (node, path_copy) 或用元组+索引方式减少内存分配。
