显式栈与状态机：替代递归的通用方法

递归把“下一步从哪里继续”保存在运行时调用栈中；显式栈把这份控制权交还给程序。本文给出从递归到 Deque<Frame> 的通用转换法，并用后序遍历、回溯和记忆化 DFS 三类例子说明何时必须加状态、如何避免遗漏回溯与结果汇总。

目录

递归到底替你做了什么

一次函数调用并不只是在“跳到另一个函数”。运行时会为它创建一个栈帧（stack frame），其中至少保存：

递归的优点是这些细节由语言运行时维护；代价是调用深度受线程栈限制，且中断、分段执行、打印执行轨迹都较难控制。

下图将“JVM 调用栈”中的信息映射为程序自己的 Deque<Frame>。关键不是复制一堆节点，而是把恢复位置明确编码成 phase：

一句话心智模型：显式栈中的一项，不是“一个待访问节点”，而是“一次尚未完成的函数调用”。phase 就是这次调用的程序计数器。

只用栈与栈 + 状态的分界

若任务在“第一次看到节点”时即可完成，例如二叉树前序遍历，压入节点即可；若任务要在子调用返回后继续，例如后序遍历、回溯撤销、合并子结果，则栈项必须保存阶段或循环下标。

何时应该改用显式栈

显式栈不是“递归一定更高级”的替代品，而是对控制流的主动建模。优先考虑它的情形如下：

不该把“防栈溢出”理解成空间从 O(h) 变成 O(1)。 两种写法都需要 O(h) 保存深度为 h 的未完成调用；区别在于递归使用受限的线程栈，显式栈使用可增长、可观测的堆对象。

转换的核心：栈帧 + 阶段

把一个递归函数拆成若干个可暂停片段。每个片段前设置 phase，再压入子调用；子调用弹出后，父帧位于栈顶，正好从该 phase 继续。

例如递归后序遍历的控制流是：

void postorder(Node node) {
    if (node == null) return;
    postorder(node.left);       // 子调用 1
    postorder(node.right);      // 子调用 2
    answer.add(node.value);     // 两个子调用都返回后执行
}

对应的帧应至少包含当前节点与三个阶段：

static final class Frame {
    final Node node;
    int phase;

    // phase = 0：刚进入，尚未处理左子树
    // phase = 1：左子树已经返回，尚未处理右子树
    // phase = 2：右子树已经返回，可以执行收尾逻辑
    Frame(Node node) {
        this.node = node;
    }
}

最关键的顺序：先把父帧的 phase 前移，再 push 子帧。否则子帧返回后，父帧仍会以旧状态再次压入同一个子任务，形成死循环。

通用转换步骤

下面这五步适用于大多数“递归函数 → 显式栈”转换。

1. 列出递归调用点。 每个递归调用点之后还有什么动作，就至少对应一个恢复阶段。
2. 提取帧字段。 参数、跨子调用仍需使用的局部变量、循环下标、子结果与撤销信息，都放入 Frame。
3. 定义阶段含义。 用注释或枚举写清 phase = 0/1/2 分别表示什么，避免“魔法数字”。
4. 以 peek() 驱动。 读取栈顶帧，根据状态推进；只有一个调用彻底结束才 pop()。
5. 先推进父帧，再压子帧。 父帧相当于被挂起的“续执行点”，它必须先记录下一次从何处恢复。

通用骨架如下；onEnter、pushNextChild 与 onExit 由具体问题填充：

Deque<Frame> stack = new ArrayDeque<>();
stack.push(new Frame(root));

while (!stack.isEmpty()) {
    Frame frame = stack.peek();

    switch (frame.phase) {
        case 0 -> {
            onEnter(frame);          // 相当于递归函数刚进入
            frame.phase = 1;         // 先记录“回来后从阶段 1 继续”
            pushNextChild(stack, frame);
        }
        case 1 -> {
            // 子调用返回后继续；必要时重复推进多个子任务
            frame.phase = 2;
            pushNextChild(stack, frame);
        }
        default -> {
            onExit(frame);           // 相当于递归函数末尾与返回值汇总
            stack.pop();
        }
    }
}

ArrayDeque 是 Java 中实现这种 LIFO 栈的合适默认选择：它实现 Deque，不允许 null，绝大多数操作为均摊 O(1)，官方文档也说明其作为栈通常快于旧的 Stack 类。Java ArrayDeque 文档

例一：二叉树后序遍历

递归版本：语义最清晰的基准

static void postorder(Node node, List<Integer> answer) {
    if (node == null) return;
    postorder(node.left, answer);
    postorder(node.right, answer);
    answer.add(node.value);
}

显式栈版本：用 phase 保存“返回位置”

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

static List<Integer> postorderIterative(Node root) {
    List<Integer> answer = new ArrayList<>();
    if (root == null) return answer;

    Deque<Frame> stack = new ArrayDeque<>();
    stack.push(new Frame(root));

    while (!stack.isEmpty()) {
        Frame frame = stack.peek();
        Node node = frame.node;

        if (frame.phase == 0) {
            frame.phase = 1;                 // 左子树返回后从阶段 1 继续
            if (node.left != null) stack.push(new Frame(node.left));
        } else if (frame.phase == 1) {
            frame.phase = 2;                 // 右子树返回后从阶段 2 继续
            if (node.right != null) stack.push(new Frame(node.right));
        } else {
            answer.add(node.value);          // 两个子树均已完成
            stack.pop();
        }
    }
    return answer;
}

static final class Frame {
    final Node node;
    int phase;

    Frame(Node node) {
        this.node = node;
    }
}

static final class Node {
    final int value;
    final Node left;
    final Node right;

    Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

这里 phase 的作用等价于三行递归代码之间的“指令位置”：阶段 0 处理左子树，阶段 1 处理右子树，阶段 2 执行后处理并返回。若只压 Node 而没有 phase，程序无法知道该节点是首次到达，还是已经从左子树返回。

例二：回溯搜索

回溯比普通遍历多了一层难点：每次向下递归前会修改共享状态，返回后必须严格撤销。以枚举数组子集为例：每个下标有“不选”和“选”两条分支。

递归版本

static void subsets(int[] nums, int index, List<Integer> path,
                    List<List<Integer>> answer) {
    if (index == nums.length) {
        answer.add(new ArrayList<>(path));
        return;
    }

    subsets(nums, index + 1, path, answer);  // 不选 nums[index]
    path.add(nums[index]);
    subsets(nums, index + 1, path, answer);  // 选 nums[index]
    path.remove(path.size() - 1);             // 撤销选择
}

显式栈版本

phase 恰好描述三件事：不选分支是否结束、选分支是否结束、是否该撤销选择。

static List<List<Integer>> subsetsIterative(int[] nums) {
    List<List<Integer>> answer = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    Deque<SubsetFrame> stack = new ArrayDeque<>();
    stack.push(new SubsetFrame(0));

    while (!stack.isEmpty()) {
        SubsetFrame frame = stack.peek();

        if (frame.index == nums.length) {
            answer.add(new ArrayList<>(path));
            stack.pop();
        } else if (frame.phase == 0) {
            frame.phase = 1;                       // 从“不选”返回后继续
            stack.push(new SubsetFrame(frame.index + 1));
        } else if (frame.phase == 1) {
            path.add(nums[frame.index]);           // 做选择
            frame.phase = 2;                       // 子调用返回后必须撤销
            stack.push(new SubsetFrame(frame.index + 1));
        } else {
            path.remove(path.size() - 1);          // 撤销与上面的 add 成对
            stack.pop();
        }
    }
    return answer;
}

static final class SubsetFrame {
    final int index;
    int phase;

    SubsetFrame(int index) {
        this.index = index;
    }
}

回溯代码的成对约束

调试技巧：在每次 push、pop、add、remove 时打印 path 与栈顶 phase。只要任意一条路径的 add/remove 不成对，后续答案就会被污染。

例三：记忆化 DFS 的显式栈

记忆化 DFS 适合“一个状态依赖多个更小状态”的问题。递归版天然会在子状态返回后读取其结果；改成显式栈时，要额外保存处理到第几个依赖，并在所有依赖完成后汇总。

以 DAG 上的最长路径为例，令 best[u] 为从 u 出发的最长边数。u 的值依赖其所有出边终点的 best[v]：

best[u] = 0                                  （u 没有出边）
best[u] = 1 + max(best[v])，v ∈ adj[u]       （否则）

帧需要从“只保存节点”升级为：

static final class DfsFrame {
    final int node;
    int nextChild;       // 下一条尚未发起的边
    int bestChild = -1;  // 已完成子状态的最大值

    DfsFrame(int node) {
        this.node = node;
    }
}

循环的关键逻辑如下（color：0 未访问、1 当前路径中、2 已完成）：

while (!stack.isEmpty()) {
    DfsFrame frame = stack.peek();
    int u = frame.node;

    if (color[u] == 0) {
        color[u] = 1;                         // ENTER：加入当前 DFS 路径
    }

    if (frame.nextChild < graph[u].size()) {
        int v = graph[u].get(frame.nextChild++); // 先推进下标，再压入子帧
        if (color[v] == 1) throw new IllegalArgumentException("图中存在环");
        if (color[v] == 0) {
            stack.push(new DfsFrame(v));
        } else {                              // color[v] == 2，直接消费缓存
            frame.bestChild = Math.max(frame.bestChild, best[v]);
        }
    } else {
        best[u] = frame.bestChild < 0 ? 0 : 1 + frame.bestChild;
        color[u] = 2;                         // EXIT：结果已可被父帧使用
        stack.pop();
        if (!stack.isEmpty()) {
            stack.peek().bestChild = Math.max(stack.peek().bestChild, best[u]);
        }
    }
}

这里的 nextChild 是多子调用场景的“程序计数器”；color == 1 既标识当前路径，也让循环依赖能在压栈前被发现。它与 动态规划 中“先计算依赖，再计算当前状态”的顺序本质相同，只是计算顺序由显式栈驱动。

正确性与复杂度

为什么两种写法等价

可用不变式理解转换：在任意时刻，显式栈从底到顶的帧序列，恰好等价于递归程序尚未返回的调用链；每个帧的字段等价于对应递归栈帧里的参数与局部变量；每个 phase 等价于该函数下一条应执行的语句位置。

循环每次要么推进栈顶帧到下一个阶段，要么压入一个与递归调用等价的子帧，要么弹出已完成帧。因此它逐步模拟递归的进入、返回和后处理，访问顺序与副作用保持一致。

最佳实践与常见陷阱

建模与实现

• 使用 Deque<Frame> stack = new ArrayDeque<>()，并始终从同一端 push/pop/peek；不要混用 addLast 与 pop，以免把 LIFO 写成混乱的双端操作。
• 帧字段只放跨子调用仍需要的信息。例如 nextChild、累加器、选择编号；能从输入重新得到的不要重复保存。
• 用 enum Phase { ENTER, AFTER_LEFT, AFTER_RIGHT, EXIT } 或具名常量替代复杂场景中的裸整数，让日志和调试器直接表达状态含义。
• 将“进入”“发起子调用”“子调用返回后的合并”“退出”分别写成小方法；一个很长的 while 循环通常难以审查。
• 对可能极深的输入设置显式限制，例如最大帧数、时间预算或取消标记；显式栈避免了线程栈溢出，但不等于输入可以无限大。

高频错误

提交前自检

1. 每一个递归调用点后面的语句，是否都有对应的 phase 或 nextChild？
2. 是否在压入子帧前保存了父帧的续执行位置？
3. 每一种共享状态修改，是否都有唯一且必达的撤销点？
4. 子结果是否在子帧弹出前写入缓存，并在父帧恢复时可见？
5. 是否用退化链、空输入、单节点、多分支和含环输入分别测试？

什么时候不要转换

保留递归往往是更好的工程选择：输入深度有可靠上界、递归表达式足够清楚、也不需要暂停/取消/外部调度时，递归代码更短且更不容易遗漏恢复状态。尤其是分治、树形 DP 的浅层结构，先写递归基准实现，再基于实际深度与运行约束决定是否转换。

对于图遍历，普通 DFS 可以先用节点栈实现；但涉及后序、Tarjan 的 low 值回传、拓扑排序完成时间或回溯搜索时，应该升级为“栈帧 + 状态”，不要用一堆布尔标记勉强拼接。相关的 DFS 使用场景见 图算法。

参考资料

• Java ArrayDeque API
• Java Deque API
• 《算法导论（第 3 版）》— 第 22 章：基本的图算法
• 图算法（DFS、后序与深度受限场景）
• 动态规划（状态依赖与记忆化求值）