2.3　把递归改写成迭代

学习目标：学完本节，你能

• 判断一段递归属于哪一类，能否直接改成循环；
• 用显式栈改写那些"依赖回程"的递归；
• 说清改写的收益与代价，知道什么时候不该改。

先修：2.1（去程与回程）、2.2（调用栈与栈溢出）。 固定术语：迭代、尾调用、显式栈。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、直觉：递归的三类，改法完全不同

2.2 节讲清了递归的代价：栈空间、函数调用开销、崩溃风险。那么能不能干脆不用递归？

答案是：要看情况，但大多数情况可以。

关键在于看回程需不需要干活。回想 2.1 节的那张图：

进入 Sum(i=0)          ┐
  进入 Sum(i=1)        │  去程：只管往下走
    进入 Sum(i=2)      │
      进入 Sum(i=3)    │
        进入 Sum(i=4)  │
        返回 0         ┘  ← 基准情形
      返回 4           ┐
    返回 7             │  回程：真正干活的地方
  返回 9               │
返回 10                ┘

回程干的事越多，改写就越麻烦。 按这个标准，递归分成三类：

本节按这三类逐一处理。

二、第一类：直接换循环

看一段典型的递归：

static int SumRecursive(int[] a, int i)
{
    if (i == a.Length) return 0;
    return a[i] + SumRecursive(a, i + 1);   // 递归结果直接参与返回
}

识别信号：SumRecursive(a, i + 1) 的返回值没有经过任何后续加工就被返回了（不是"算完之后再乘以 n"那种）。这类递归，回程几乎不干活。

改写成循环：

static int SumIterative(int[] a)
{
    int s = 0;
    foreach (var x in a) s += x;
    return s;
}

改写方法（三步）：

1. 把"去程累积的东西"变成循环变量。 这里 i 变成 foreach 的迭代变量。
2. 把"回程要做的事"提前到循环体里做。 这里回程做的是 a[i] + ...，改成循环里直接 s += x。
3. 基准情形变成循环的终止条件。 i == a.Length 就是 foreach 自然结束。

实测对比（50 万个元素求和）：

  递归版（64 MB 栈）:    11.12 ms   结果 = 500,000
  循环版             :     0.48 ms   结果 = 500,000
  循环快 23.3 倍

注意这里的对比有多不公平：

• 循环版：什么都不用做，直接跑。
• 递归版：得先把线程栈从默认的 1 MB 调到 64 MB（否则 1.6 万层就崩），再花 23 倍的时间。

50 万个元素需要 64 MB 栈。 那 500 万个呢？640 MB —— 到那时调大栈已经不是选项了。这就是第一类递归应该被改写的理由。

三、第二类：用变量记住中间状态

斐波那契的递归版本有两个问题叠在一起：

static long FibRecursive(int n)
{
    if (n <= 1) return n;
    return FibRecursive(n - 1) + FibRecursive(n - 2);   // 重复计算！
}

1. 栈开销：深度是 $n$，$n = 40$ 时深度只有 40，还不算危险。
2. 重复计算：这是真正致命的问题 —— Fib(n-2) 在 Fib(n-1) 里已经被算过一遍了。

改成迭代：

static long FibIterative(int n)
{
    if (n <= 1) return n;

    long prev = 0, curr = 1;          // 只保留最近两个值
    for (int i = 2; i <= n; i++)
    {
        long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

关键洞察：只需保留最近两个值。

斐波那契的每一项只依赖前两项，所以算第 $i$ 项时，第 $i-3$ 项及更早的结果全都可以扔掉。

这带来一个额外的好处：空间复杂度从 $O(n)$ 降到 $O(1)$ ——注意，递归版本的空间是 $O(n)$（调用栈深度），一个更"朴素"的迭代表格版本（用一个数组存所有项）也是 $O(n)$，而这个滚动变量的版本只有 $O(1)$。

实测对比：

  Fib(30) = 832,040      | 递归      3.11 ms | 迭代   0.0665 ms | 一致=True
  Fib(35) = 9,227,465    | 递归     33.51 ms | 迭代   0.0003 ms | 一致=True
  Fib(40) = 102,334,155  | 递归    264.23 ms | 迭代   0.0009 ms | 一致=True

$n$ 从 30 涨到 40（涨 33%），递归耗时涨了 85 倍（3.11 ms → 264.23 ms），而迭代版的耗时几乎不变。

关于 0.0003 ms 这个数字：它已经接近 Stopwatch 的精度极限，几次测量之间会有明显抖动（所以 Fib(35) 反而比 Fib(40) 显示得更小）。这不是错误，而是"迭代版快到测不出来"。

这正是量级差异的直观体现：当两个版本的差距达到十万倍时，精确的数字已经不重要了。

四、第三类：需要显式栈

现在看一个回程真的要干活的例子：把十进制转成二进制。

// 递归版
static void ToBinaryRecursive(int n)
{
    if (n == 0) return;
    ToBinaryRecursive(n / 2);
    Console.Write(n % 2);       // 写在递归调用【之后】-> 回程执行
}

为什么这个不能简单改成循环？

因为余数是反着出来的。以 $n = 10$ 为例：

算出余数的顺序是 0, 1, 0, 1，但二进制的正确写法是 1010 —— 正好相反。

递归天然解决了这件事：它在去程把余数算出来，压进调用栈；在回程把它们倒着打印出来。

用显式栈改写：

static void ToBinaryIterative(int n)
{
    var stack = new Stack<int>();
    while (n > 0)
    {
        stack.Push(n % 2);           // 余数入栈
        n /= 2;
    }
    while (stack.Count > 0)
        Console.Write(stack.Pop());  // 出栈顺序正好是倒序
}

改写方法：递归靠调用栈自动保存的数据，改成用一个你自己的栈显式保存。

• 原来的"去程"→ 第一个 while 循环：算出余数，压栈
• 原来的"回程"→ 第二个 while 循环：出栈，正好得到相反的顺序

实测输出：

        10 -> 1010  (递归)   1010  (显式栈)
       255 -> 11111111  (递归)   11111111  (显式栈)
      1024 -> 10000000000  (递归)   10000000000  (显式栈)
    123456 -> 11110001001000000  (递归)   11110001001000000  (显式栈)

两种写法结果完全一致。

这个技巧在第 9 章会大量使用：二叉树的三种深度优先遍历，都可以用"显式栈 + 状态标记"改写成迭代版本。9.2 节会给出统一模板。

五、改写收益与代价对照表

注意第三类的迭代版：它虽然也叫"用栈"，但用的是堆上的 Stack<T>，不是线程栈。堆有几个 GB 可用，而且可以主动监控大小。这就是为什么"显式栈"能解决问题 —— 它换了一个容量大得多的资源池。

什么时候不该改写？

1. 深度确定很小（比如树的深度不超过 100）。递归的可读性收益更大。
2. 深度是 $O(\log n)$。 二分查找、平衡树操作都属于这类 —— $n$ 涨到 10 亿，深度也才 30。这类递归永远安全，不要改。
3. 改写后明显更难维护，而收益不确定。 比如第三类里嵌套很深的回溯算法，手写显式栈极易出错。

决策顺序：先估深度随 $n$ 怎么增长 → 深度可控就保留递归 → 不可控就改写 → 第三类优先考虑用受控的栈大小 + 深度上限检查兜底（见 2.2 节练习 2.2.5）。

六、练习

练习 2.3.1（分类） 下面四个递归分别属于本节说的哪一类（①直接换循环 / ②用变量 / ③需要显式栈）？

// (a) 求数组最大值
static int Max(int[] a, int i)
{
    if (i == a.Length - 1) return a[i];
    return Math.Max(a[i], Max(a, i + 1));
}

// (b) 计算阶乘
static long Fact(int n)
{
    if (n <= 1) return 1;
    return n * Fact(n - 1);
}

// (c) 逆序打印数组
static void PrintReverse(int[] a, int i)
{
    if (i == a.Length) return;
    PrintReverse(a, i + 1);
    Console.Write(a[i] + " ");
}

// (d) 计算爬楼梯方案数（每次走 1 或 2 级，求走到第 n 级的走法数）
static long Climb(int n)
{
    if (n <= 2) return n;
    return Climb(n - 1) + Climb(n - 2);
}

练习 2.3.2（改写） 把上面的 (a) 和 (c) 改写成迭代版本。

练习 2.3.3（判断该不该改） 下面三种情况，哪些应该改写递归？说明理由。 (a) 一个处理评论树的方法，评论最多嵌套 5 层 (b) 一个求幂函数 Power(b, e)，递归深度是 $\log_2 e$ (c) 一个解析 JSON 的递归下降解析器，嵌套深度取决于用户输入

练习 2.3.4（挑战·为什么能省空间） 第二类改写（斐波那契用滚动变量）把空间从 $O(n)$ 降到了 $O(1)$。请说明：为什么这个技巧在其他递归上不一定管用？ 举一个用不了的例子。

练习 2.3.5（挑战·改写） 把下面的递归改写成迭代版本。这是"第三类"的一个变体：回程需要按相反顺序处理数据，但数据不是简单压栈就能还原的。

// 判断一个字符串是不是"回文"
static bool IsPalindrome(string s, int lo, int hi)
{
    if (lo >= hi) return true;
    if (s[lo] != s[hi]) return false;
    return IsPalindrome(s, lo + 1, hi - 1);
}

七、练习答案

2.3.1

• (a) 第一类。 Max(a, i+1) 的结果直接参与 Math.Max 后就返回了 —— 等等，它经过了加工（取了最大值）。但加工只需要一个临时值，不需要保存历史。所以它属于第一类：循环里用一个 best 变量滚动更新即可。

  判断要点：回程干的活是不是"只需要当前这一层的数据 + 一个累积值"？是的话就是第一类。

• (b) 第一类。 阶乘是"回程乘以 $n$"。可以改成正向循环累乘。
• (c) 第三类。 回程按相反顺序打印，且必须保存所有元素。这需要显式栈（或者一个数组 + 反向遍历）。
• (d) 第二类。 和斐波那契完全同构（爬楼梯的方案数就是斐波那契数列的偏移），只依赖前两个状态，用两个变量即可。

2.3.2

(a) 求最大值：

static int MaxIterative(int[] a)
{
    int best = a[0];
    for (int i = 1; i < a.Length; i++)
        if (a[i] > best) best = a[i];
    return best;
}

要点：把"回程取最大值"改成"去程就不断更新 best"。因为取最大值这个操作满足结合律，先算后算结果一样。

(c) 逆序打印：

// 方案一：直接反向遍历（最简单，不需要栈）
static void PrintReverseSimple(int[] a)
{
    for (int i = a.Length - 1; i >= 0; i--)
        Console.Write(a[i] + " ");
}

// 方案二：用显式栈（更通用，适合"必须按处理顺序压入"的场景）
static void PrintReverseStack(int[] a)
{
    var stack = new Stack<int>();
    foreach (var x in a) stack.Push(x);
    while (stack.Count > 0) Console.Write(stack.Pop() + " ");
}

优先选方案一。 只有当"数据的产生顺序"和"处理顺序"天然相反、且无法直接反向访问时（比如数据是流式产生的），才需要方案二。

这条经验很重要：改写之前，先问一句"有没有更简单的写法"。很多看起来需要栈的问题，其实一个反向遍历就够了。

2.3.3

• (a) 不需要改写。 深度固定上限 5 层，永远不会溢出。递归版本更贴合"树"这个数据结构的自然形态，可读性明显更好。这是"深度可控"的典型场景。
• (b) 不需要改写。 深度是 $O(\log n)$，$e = 10^{18}$ 时深度也才 60 层。这类递归永远安全。

• (c) 必须改写（或至少加防护）。 深度取决于用户输入，这是一个不可信的外部因素。攻击者可以构造一个嵌套 10 万层的 JSON，直接让服务崩溃 —— 这是一个真实的拒绝服务（DoS）漏洞。

  这一条特别值得记住：当递归深度由用户输入决定时，它就不再是"性能问题"，而是"安全问题"。 正确做法是：在解析器中记录当前深度，超过阈值（比如 100）就返回错误。

2.3.4

原因是：滚动变量能省空间的前提，是"每个状态只依赖固定数量的前驱状态"。

斐波那契的第 $i$ 项只依赖第 $i-1$ 和 $i-2$ 项，所以更早的项可以安全丢弃。

用不了的例子：

1. 0/1 背包问题：每个状态依赖"上一轮的所有容量"和"当前物品"。压缩成一维是可以的，但必须改变遍历方向（15.4 节会详细讲这个技巧）。它不是"两个变量"就能解决的。

2. 最长递增子序列（LIS）的 $O(n^2)$ 解法：dp[i] 需要和前面所有的 dp[j]（$j < i$）比较。每个状态依赖 $O(n)$ 个前驱，无法用固定几个变量表示。

3. 编辑距离：dp[i][j] 依赖 dp[i-1][j]、dp[i][j-1] 和 dp[i-1][j-1] 三个方向。它可以从二维压到一维，但要小心保存被覆盖的值（同样是 15.4 节的内容）。

通用规律：能压缩到什么程度，取决于状态依赖的"宽度"。

• 依赖固定的前 $k$ 个状态 → 用 $k$ 个变量，空间 $O(1)$
• 依赖上一整行 → 用两个一维数组滚动，空间从 $O(n^2)$ 降到 $O(n)$
• 依赖前面所有状态 → 无法压缩

2.3.5

static bool IsPalindromeIterative(string s)
{
    int lo = 0, hi = s.Length - 1;
    while (lo < hi)
    {
        if (s[lo] != s[hi]) return false;
        lo++;
        hi--;
    }
    return true;
}

关键点：这个改写根本不需要栈。

虽然它是"第三类"的形态（回程要处理数据），但这里有个特殊性质：回程做的事（比较 s[lo] 和 s[hi]）不依赖任何累积结果，而且两个下标都可以从两端向中间逼近。

原递归版本里的 lo + 1 和 hi - 1 其实就是两个指针 —— 只是被递归的参数传递给"藏"起来了。把它们提出来变成循环变量，改写就完成了。

这是改写时最常出现的顿悟：递归参数往往就是循环变量。 递归用"参数 + 调用栈"来记录进度，迭代用"变量 + 循环"来记录进度。两者记录的信息是完全一样的，只是存放的位置不同。

所以改写的第一步永远是：列出递归的所有参数，问自己"它们各自记录了什么进度"。

八、常见错误

九、本节总结

1. 递归按回程干什么活分成三类，改法完全不同：
   • ① 回程不干活 → 直接换循环（求和、阶乘、找最大值）
   • ② 回程只用固定几个值 → 用滚动变量（斐波那契，顺带降空间）
   • ③ 回程要按相反顺序处理全部数据 → 用显式栈（转二进制、树遍历）
2. 递归参数往往就是循环变量。 改写的第一步是列出参数，问清每个参数记录了什么进度。
3. 实测差距：求和循环快 23.3 倍且不需要 64 MB 栈；Fib(40) 迭代比递归快约 30 万倍。
4. 显式栈的本质是换资源池：从 1 MB 的线程栈换到几 GB 的堆。
5. 不是所有递归都该改。 深度 $O(\log n)$ 或上限可控时，递归的可读性更值钱。
6. 深度由用户输入决定时，这是安全问题而不是性能问题。

下一节衔接：到目前为止，我们的递归都是"把问题缩小一点"（$n \to n-1$）或者"沿着一条路走到底"。还有第三种用法 —— 把问题一刀切成两半，两边都解决，再把结果合起来。这种模式叫分治，它是归并排序、快速排序、快速幂的共同骨架，也是本章的收尾。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "2.3",
  "title": "把递归改写成迭代",
  "covered": [
    "按「回程干什么活」划分的三类递归",
    "第一类：直接换循环的三步改写法",
    "第二类：滚动变量（斐波那契，空间 O(n) -> O(1)）",
    "第三类：显式栈（十进制转二进制）",
    "改写收益与代价对照表",
    "「递归参数往往就是循环变量」这条通用规律",
    "用户输入决定深度 = DoS 漏洞"
  ],
  "unresolved": [
    "0/1 背包与 LIS 的状态依赖宽度留到 15.3-15.4",
    "树的迭代遍历统一模板留到 9.2",
    "受控深度上限的兜底方案见 2.2 节练习 2.2.5"
  ],
  "canonical_terms": {
    "迭代": "用循环重复执行，不使用函数自我调用",
    "尾调用": "递归调用是函数的最后一个动作，返回值直接向外传递",
    "显式栈": "由程序员在堆上创建和管理的栈，用于替代调用栈"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 2.1 的去程/回程与 2.2 的调用栈",
    "读者会使用 Stack<T> 的基本操作（第 5 章会详解）"
  ],
  "word_count_actual": 2010,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch02/Sec23/",
    "实测数据逐项核对：11.12ms/0.48ms(23.3倍)、Fib(40) 264.23ms/0.0009ms",
    "二进制转换的递归版与显式栈版输出逐项一致",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初稿用 100 万元素 + 32 MB 栈，实测仍崩溃（524010 层溢出）；已降为 50 万元素 + 64 MB 栈并重测通过",
    "Fib(35) 迭代耗时(0.0003ms)小于 Fib(40)(0.0009ms)，属计时器精度噪声，已在正文说明"
  ],
  "next": "2.4 分治：切开、解决、合并"
}