递归如何变成迭代：显式栈、继续执行的位置与算法取舍

从隐式调用栈到显式状态管理

本篇覆盖知识点 38—42。先比较思考方式，再把求和和树的后序遍历改成循环，观察到底保存了哪些状态，以及空间是否真的减少。

知识点 38：推进方向不是迭代与递归的定义

《Hello 算法》的求和示例，用循环从 1 加到 n，用递归从 n 拆到基本情况，所以分别呈现自下而上与自上而下的思考方式。这是一种有用的教学对比，不是语法定义。

循环也可以从 n 减到 1；尾递归也可以在深入过程中积累已有结果。要判断机制，应看“同一次调用里的循环推进”还是“创建下一次调用”，而不是数字向上还是向下。

同一个答案也不能证明两份程序完全等价：如果包含打印、修改共享对象、异常或清理，执行顺序同样属于可观察行为。转写前应确定要保留的是最终数值、遍历顺序，还是完整动作轨迹。

知识点 39—40：入栈模拟深入，出栈模拟返回

普通求和递归把当前 n 保留在调用帧中，等待较小问题返回后再相加。显式栈版本把 3、2、1 依次压入列表，接着按 1、2、3 的顺序取出累加。Python 列表的 append 和尾部 pop 可以表达后进先出。

这里每层只需保存一个数，因为“返回后相加”这个动作已经统一写在循环里。复杂递归不一定如此；下一节会把“返回后还要做什么”也放进栈。

下面约定 n 为非负整数，打印结果为 6。

def sum_with_stack(n):
    if type(n) is not int or n < 0:
        raise ValueError("n must be a non-negative integer")
    pending = []
    for value in range(n, 0, -1):
        pending.append(value)
    total = 0
    while pending:
        total += pending.pop()
    return total

print(sum_with_stack(3))

复杂场景：后序遍历还要保存继续执行的位置

树的后序遍历顺序是左子树、右子树、当前节点。递归中，父调用知道自己尚未执行“记录当前节点”。改成显式栈时，如果只保存节点，弹出时就不知道该先展开子树，还是子树已经结束、该记录节点。

下面把每个待处理项写成 (node, expanded)。expanded=False 表示要展开；True 表示子树安排过了，轮到当前节点。它保存的正是递归函数的继续执行阶段。

栈后进先出，所以先压入“当前节点的返回阶段”，再压右子树，最后压左子树。这样实际弹出顺序才是左、右、当前。示例树为 A 的左子树 B（孩子 D、E）及右子树 C；两种实现都输出 D、E、B、C、A。

本例的树有限、无环，节点用 (值, 左子树, 右子树) 的元组表示，空子树为 None。返回列表是输出空间；显式栈是工作空间，应分别计算。

tree = ("A", ("B", ("D", None, None), ("E", None, None)),
        ("C", None, None))

def postorder_recursive(node):
    values = []
    def visit(current):
        if current is None:
            return
        value, left, right = current
        visit(left)
        visit(right)
        values.append(value)
    visit(node)
    return values

def postorder_stack(node):
    values = []
    pending = [(node, False)]
    while pending:
        current, expanded = pending.pop()
        if current is None:
            continue
        value, left, right = current
        if expanded:
            values.append(value)
        else:
            pending.append((current, True))
            pending.append((right, False))
            pending.append((left, False))
    return values

print(postorder_recursive(tree))
print(postorder_stack(tree))

知识点 41：状态搬到列表，不等于状态消失

把调用帧换成列表，只是改变了状态存放和管理的位置。求和的显式栈仍保留 n 个数，因此额外空间仍为 O(n)。直接循环累加没有未完成的逐层操作，可以省去栈，只维护固定数量的变量。

上述 O(1) 或 O(n) 的常见空间表述按固定大小的数值状态模型理解；Python 整数实际位数另计。树遍历则应以节点数 N 和高度 H 分析：这两个后序实现各访问节点线性次数，工作栈峰值为 O(H)，另有 O(N) 的结果列表。退化成链的树可能有 H=N，不能总把树高假定为 log N。

知识点 42：以问题结构和运行约束做选择

线性累计、轮询等问题通常可以直接循环推进；树遍历、分治和回溯的代码经常适合递归表达，因为每层剩余工作自然由调用状态保存。输入可能形成很深的路径时，显式栈便于管理深度、暂停阶段和诊断信息，但代码也可能更复杂。

遍历图还要处理重复访问和环。A→B→A 这样的路径，如果不断沿边递归且没有访问控制，就不会因为“走到了较小子图”自动结束。递归或显式栈都需要与算法目标相配合的 visited 集合、路径状态或其他去重策略。

对有限图的普通可达性 DFS，把节点标记为已访问后再展开邻居，可以避免无休止重复进入。环检测等任务可能还需要区分“当前路径中”与“已完成”的状态。调用方式不会替代这些算法要求。

工程选择顺序：明确需要保持的结果和动作顺序；分析最深路径与需要保留的状态；核对运行时限制；再比较可读性、维护成本和必要的实际性能证据。不能从“递归通常有调用开销”推出所有递归实现都比任何循环算法慢。

复盘：把结果、轨迹和空间分别核验

1. 为什么显式栈求和仍需要线性空间，而直接循环可以省去栈？
2. 后序遍历如果先压左子树再压右子树，会怎样改变输出？
3. expanded 标记在模拟递归帧中的哪份信息？
4. 无论递归还是循环，图中的环需要怎样处理？

建议用空输入、单节点、单链和有左右分支的树比较两种后序遍历：结果列表和顺序都应一致。对求和，用 n=0…20 与 n(n+1)/2 的独立计算结果核对。几个样例可以检查实现，空间阶数仍需结合状态数量推导。

基础机制：Python 列表作为栈 ↗ · 执行帧 ↗ · 解释器深度限制 ↗。算法转换和空间比较由本文代码推导。

上一篇 · 返回总索引 · 在学习地图中复盘

本系列的来源与许可

本篇是《Hello 算法》相关主题的重新组织与补充讲解。署名、修改说明及 CC BY-NC-SA 4.0 许可见 系列来源说明；对应知识点和官方依据均可从索引核验。