递归代码很短，是因为运行时替你保存了“做到哪里、局部变量是什么、子调用返回后从哪继续”。这些信息位于调用栈的栈帧中。理解它们，才能解释输出顺序、空间复杂度和栈溢出。

“递”和“归”是两个阶段

考虑计算数组前 n 项之和：

long long sumPrefix(const std::vector<int>& values, int n) {
    if (n == 0) return 0;
    long long rest = sumPrefix(values, n - 1);
    return rest + values[n - 1];
}

sum-prefix.cpp

输入 n=3 时，执行顺序可以写成：

sum(3) 等待 sum(2)
  sum(2) 等待 sum(1)
    sum(1) 等待 sum(0)
      sum(0) 返回 0
    sum(1) 返回 0 + a[0]
  sum(2) 返回 sum(1) + a[1]
sum(3) 返回 sum(2) + a[2]

向下建立调用链是“递”，从基本情况逐层恢复答案是“归”。递归前的语句按从外到内执行，递归后的语句按从内到外执行。

EX示例 · 前序与后序输出

void trace(int n) {
    if (n == 0) return;
    std::cout << "enter " << n << '\n';
    trace(n - 1);
    std::cout << "leave " << n << '\n';
}

trace(3) 先输出 enter 3,2,1，再输出 leave 1,2,3。leave 的逆序并不是特殊语法，而是栈帧后进先出的结果。

一个栈帧保存什么

一次普通函数调用通常需要保存：

• 实参或参数值；
• 局部变量；
• 返回地址；
• 必要的寄存器和运行时状态。

因此空间复杂度取决于同时存活的最深调用链，而不是总调用次数。完整二叉递归可能有 $O(n)$ 个结点，但若每次规模减半，深度只有 $O(\log n)$。

O(·)复杂度 · 总工作量与调用深度是两件事

归并排序总共有 $O(n)$ 个递归结点，时间为 $O(n\log n)$，但任意时刻只沿一条根到叶路径加上辅助数组，调用栈深度为 $O(\log n)$。若把“结点数”误当“栈深度”，空间分析就会出错。

递归树怎样帮助观察重复工作

递归树把一次调用画成结点，把子调用画成子结点。它可以回答两个不同问题：

1. 每层一共有多少工作？
2. 同一个参数状态是否多次出现？

朴素 Fibonacci 的 fib(5) 会在不同分支重复出现 fib(3)、fib(2)。递归树揭示指数级重复；记忆化则把相同参数的结点合并为状态图。

相反，归并排序的两个半区互不重叠。它有许多调用，但没有对同一区间重复排序。此时缓存区间答案没有意义，优化重点在合并和内存复用。

自相似图形：顺序也是答案的一部分

12E03 · 南蛮图腾先取得规模 n-1 的图，再把它复制到上、左下和右下位置。若直接在递归中打印，很难回到上方修改已经输出的行；因此“返回一组字符串，再在归阶段组合”更符合合同。

这一设计体现了一个通用原则：

PROP性质 · 数据依赖决定递归前后顺序

若当前操作只依赖参数，可放在递归之前；若它依赖子问题的结果，必须在子调用返回后执行。不要凭习惯选择前序或后序。

何时改写为循环

线性递归通常可以直接改成循环。前缀和递归每次只进入唯一的 n-1，返回阶段只做一次加法，因此循环更节省栈空间：

long long sumPrefix(const std::vector<int>& values, int n) {
    long long answer = 0;
    for (int i = 0; i < n; ++i) answer += values[i];
    return answer;
}

sum-prefix-iterative.cpp

改写时保留原合同，并寻找“栈中哪些状态其实可以压成几个变量”。若每个栈帧只保存下一步下标和一个累加器，循环通常足够。

WARN易错点 · 不要假设 C++ 会优化尾递归

C++ 标准不保证尾调用优化。即使递归调用是最后一个动作，编译器也可能保留每个栈帧。输入规模可能达到十万或百万时，不应把程序安全寄托在尾递归优化上。

何时需要显式栈

树或图的深度优先遍历可能有多个子分支，简单 for 循环无法保存“处理到第几个孩子”。显式栈可以把隐式栈帧变成可控制的数据结构：

struct Frame {
    int node;
    int nextChild;
};

若算法需要在所有孩子处理完后再合并，还要给帧保存阶段标记或下一孩子下标。显式栈的优势是容量可控、状态可观察；代价是代码更长，必须亲自维护入栈与退栈不变量。

逆向定位：不用展开整棵递归树

12E06 · Secret Cow Code中的字符串长度指数增长，但题目只问一个位置。正确策略是先找到覆盖目标位置的最小长度，再把位置逐层映射回前一半。

这相当于从递归树的一片叶子向根反推，只沿一条路径走，时间 $O(\log N)$、空间 $O(1)$。它提醒我们：题面描述了递归生成过程，并不代表程序必须生成所有中间对象。

ANTI反例 · 按定义真实拼接到 N

当 N=10^18 时，即便每秒生成十亿字符也远不可行。构造算法应由所需输出决定：只查询一个字符，就只追踪一条索引路径。

自检

1. 递归函数调用了百万次，是否一定需要百万个栈帧？
2. 为什么后序操作会按与进入相反的顺序执行？
3. 把递归改成显式栈后，空间复杂度会自动降低吗？

参考答案

1. 不一定。栈帧数取决于最大同时调用深度；一百万个分支若逐个完成，深度可能很小。线性递归深度才可能等于调用次数。
2. 外层栈帧必须等待内层返回；最后进入的内层最先完成，符合栈的后进先出顺序。
3. 不会。显式栈通常保存与隐式栈相同的信息，渐进空间仍相同；它主要提供更可控的存储位置，并避免受线程调用栈大小限制。

延伸阅读

• Hello 算法：迭代与递归对比两种控制流并展示递归树。
• 下一节分治建模将调用机制提升为算法设计框架。