第 2 章　递归与分治

本章解决的问题：为什么你"看得懂递归，却写不出递归"？以及为什么有些递归能跑，有些一跑就崩？

2.1　递归的两个必要条件

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

• 说出递归的两个必要条件，并判断一段递归代码是否满足；
• 画出一次递归的「去程」与「回程」，说清结果是在哪一程算出来的；
• 独立写出求和、阶乘、字符串反转等基础递归函数。

先修：会写方法、if，理解 1.2 的大 O 入门概念。 固定术语：递归、基准情形、递归情形、规模缩减。 环境与版本：.NET 8 / C# 12。 预计阅读：25 分钟。

一、直觉：电影院里的问题

你在电影院，想知道自己坐在第几排，但懒得起立去数。

你拍前面那人的肩膀："你坐第几排？" 他也不知道，于是他拍他前面的人。（递归调用） …… 一直问到第一个人，他回答："我是第 1 排。"（基准情形） 然后答案一层层传回来：第 2 排 → 第 3 排 → …… → 轮到你。

这个例子里藏着递归的全部要点：

• 基准情形：第 1 排的人直接给出答案，不再往前问。没有他，问题就永远问不完。
• 递归情形：其他每个人做的都是同一件事 —— "问前面的人，再把结果 +1"。
• 规模缩减：每次都问"更前面的一个人"，离第 1 排越来越近。

递归的写法之所以难，是因为它的执行顺序和你的阅读顺序不一样。 你读到的是"问前面的人"，但真正算出结果是在答案往回传的那一程。本节会用一段能打印过程的代码，把这"两程"直接画给你看。

二、形式化：两个必要条件

递归（Recursion）：函数直接或间接地调用自身来解决问题。

任何正确的递归必须同时满足两个条件：

条件 ① 大多数人都记得。条件 ② 才是真正容易翻车的地方，看两个反例：

// 反例 1：规模从未缩小
static int Bad(int n)
{
    if (n == 0) return 0;      // 基准情形写对了
    return Bad(n);             // 但传的还是 n，永远到不了 0
}

// 反例 2：规模在变大
static int AlsoBad(int n)
{
    if (n == 0) return 0;
    return AlsoBad(n + 1);     // 越走越远，同样是永远到不了
}

两段代码都有基准情形，但都永远停不下来。

写递归之前，先问自己两个问题：

1. 什么时候停？（基准情形）
2. 每次有没有更靠近停？（规模缩减）

这两句话能挡掉绝大多数"写出来就崩"的递归。

三、例题：把一次递归完整画出来

新建控制台项目，粘贴以下代码：

// ---------- 例 1：递归求和，并把完整调用过程打印出来 ----------
static int SumWithTrace(int[] a, int i, int depth)
{
    string indent = new string(' ', depth * 2);
    Console.WriteLine($"{indent}进入 Sum(i={i})");

    if (i == a.Length)
    {
        Console.WriteLine($"{indent}返回 0   <- 基准情形，不再递归");
        return 0;
    }

    int rest = SumWithTrace(a, i + 1, depth + 1);   // 递归情形：问题缩小到 i+1
    int result = a[i] + rest;
    Console.WriteLine($"{indent}返回 {result}");
    return result;
}

// ---------- 例 2：阶乘 ----------
static long Factorial(int n)
{
    if (n <= 1) return 1;             // 基准情形
    return n * Factorial(n - 1);      // 递归情形：规模从 n 缩到 n-1
}

// ---------- 例 3：反转字符串 ----------
static string Reverse(string s)
{
    if (s.Length <= 1) return s;              // 基准情形：空串或单字符
    return Reverse(s.Substring(1)) + s[0];    // 递归情形：去掉首字符
}

// ---------- 例 4：朴素斐波那契（为 15.1 节埋伏笔） ----------
long fibCalls = 0;

long Fib(int n)
{
    fibCalls++;
    if (n <= 1) return n;
    return Fib(n - 1) + Fib(n - 2);
}

// ==================== 主流程 ====================

int[] data = { 1, 2, 3, 4 };
Console.WriteLine("=== 例 1：递归求和的完整调用过程 ===");
Console.WriteLine($"数组: [{string.Join(", ", data)}]");
Console.WriteLine();
int total = SumWithTrace(data, 0, 0);
Console.WriteLine();
Console.WriteLine($"最终结果: {total}");

Console.WriteLine();
Console.WriteLine("=== 例 2：阶乘 ===");
foreach (int n in new[] { 0, 1, 5, 10, 20 })
    Console.WriteLine($"  {n,2}! = {Factorial(n)}");

Console.WriteLine();
Console.WriteLine("=== 例 3：反转字符串 ===");
foreach (var s in new[] { "(空串)", "a", "ab", "hello", "算法" })
{
    string input = s == "(空串)" ? "" : s;
    Console.WriteLine($"  \"{input}\" -> \"{Reverse(input)}\"");
}

Console.WriteLine();
Console.WriteLine("=== 例 4：朴素斐波那契的递归调用次数 ===");
foreach (int n in new[] { 20, 25, 30, 35 })
{
    fibCalls = 0;
    long r = Fib(n);
    Console.WriteLine($"  Fib({n,2}) = {r,-9} 递归调用次数 = {fibCalls,12:N0}");
}

实测输出（.NET 8 Release）：

=== 例 1：递归求和的完整调用过程 ===
数组: [1, 2, 3, 4]

进入 Sum(i=0)
  进入 Sum(i=1)
    进入 Sum(i=2)
      进入 Sum(i=3)
        进入 Sum(i=4)
        返回 0   <- 基准情形，不再递归
      返回 4
    返回 7
  返回 9
返回 10

最终结果: 10

=== 例 2：阶乘 ===
   0! = 1
   1! = 1
   5! = 120
  10! = 3628800
  20! = 2432902008176640000

=== 例 3：反转字符串 ===
  "" -> ""
  "a" -> "a"
  "ab" -> "ba"
  "hello" -> "olleh"
  "算法" -> "法算"

=== 例 4：朴素斐波那契的递归调用次数 ===
  Fib(20) = 6765      递归调用次数 =       21,891
  Fib(25) = 75025     递归调用次数 =      242,785
  Fib(30) = 832040    递归调用次数 =    2,692,537
  Fib(35) = 9227465   递归调用次数 =   29,860,703

四、读懂例 1：递归分"两程"

把例 1 的输出竖着看，它分成明显的两段：

进入 Sum(i=0)          ┐
  进入 Sum(i=1)        │
    进入 Sum(i=2)      │  去程：一路调用下去
      进入 Sum(i=3)    │  此时一个结果都还没算出来
        进入 Sum(i=4)  │
        返回 0         ┘  ← 撞上基准情形，去程结束
      返回 4           ┐
    返回 7             │  回程：从基准情形开始
  返回 9               │  一层层往回算
返回 10                ┘

这是理解递归最重要的一张图。 它解释了三件事：

1. 为什么基准情形是必需的 —— 没有它，去程永远不结束，程序会一直调用下去直到崩溃（2.2 节会亲眼看到这个崩溃）。
2. 为什么结果是在回程才算出来的 —— 返回 10 是最后一行，因为最外层的 Sum(i=0) 必须等里面全部算完才能加自己的 a[0]。
3. 为什么递归的空间开销是"深度" —— 在去程结束的那一刻，同时有 5 个 Sum 调用活着，每一个都在等着里面返回。它们都占着内存。这笔账在 2.2 节算清楚。

把它和循环对照一下：如果写成循环，你只需要一个 s 变量从头加到尾，全程只有 1 份状态。而递归版本在去程最深时有 5 份状态同时存在。这就是递归"用空间换简洁"的本质。

五、例 4 的警告：指数级的递归

例 4 的输出值得单独看一眼：

$n$ 只涨一点点，调用次数就涨十倍以上。 $n$ 每增加 1，调用次数大约乘以 1.618（也就是黄金比例）。

问题出在这里：Fib(n-1) 和 Fib(n-2) 会重复计算同一批子问题。Fib(35) 里的 Fib(30) 被算了不止一次，Fib(20) 更是被算了上千次。

                    Fib(5)
                  /        \
            Fib(4)           Fib(3)
           /      \         /      \
      Fib(3)     Fib(2)  Fib(2)   Fib(1)
      /    \      ...      ...      ...
   Fib(2) Fib(1)

这幅图里 Fib(3) 出现了 2 次，Fib(2) 出现了 3 次。$n$ 越大，重复得越离谱。

怎么修？ 把算过的结果存起来，下次直接查表 —— 这叫记忆化（Memoization），是 15.1 节的主题。现在你只需要记住："递归写法很简洁"和"递归写法很快"是两回事。

六、练习

练习 2.1.1（找基准情形） 为下面的问题各写出基准情形是什么： (a) 递归计算数组元素之和 (b) 递归计算 $x^n$ (c) 递归求一个链表中节点的个数（链表在 4.1 节讲，这里只需知道 node.Next 指向下一个节点，末尾是 null）

练习 2.1.2（找错） 下面三个递归函数都有问题，指出各自违反了哪个必要条件：

// (a)
static int F1(int n) { return F1(n - 1) + 1; }

// (b)
static int F2(int n) { if (n == 0) return 0; return F2(n + 1); }

// (c)
static int F3(int n) { if (n == 0) return 0; return F3(n / 2) + F3(n / 3); }

练习 2.1.3（写代码） 不用循环，写一个递归函数 CountDown(int n)，从 $n$ 倒数打印到 1，然后打印 "发射！"。 例如 CountDown(3) 输出：

3
2
1
发射！

练习 2.1.4（去程还是回程） 下面的递归函数打印出来的顺序是什么？先在心里推一遍，再实际跑一次验证。

static void Mystery(int n)
{
    if (n == 0) return;
    Console.WriteLine(n);      // 位置 A
    Mystery(n - 1);
    Console.WriteLine(n);      // 位置 B
}

调用 Mystery(3) 会输出什么？如果把位置 A 和 B 的两行交换，结果会变吗？

练习 2.1.5（挑战·数一数） 在 2.1 节例 1 的 SumWithTrace 中，处理一个长度为 $n$ 的数组时： (a) 一共创建了多少个 SumWithTrace 的调用？ (b) 在"去程最深"的那一刻，同时有多少个调用活着？ (c) 如果数组长度是 100 万，这个函数能跑吗？为什么？

七、练习答案

2.1.1

• (a) 数组为空（下标等于长度）。此时和是 0。
• (b) 指数为 0。此时 $x^0 = 1$。（注意 $x = 0$ 时 0^0 有争议，工程上按 1 处理即可。）
• (c) 节点为 null。此时节点个数是 0。

规律：基准情形通常对应"问题小到不需要再拆"的那个状态 —— 空数组、指数 0、空链表。先想清楚"什么情况下答案显而易见"，那就是你的基准情形。

2.1.2

• (a) 两个条件都违反了。 没有基准情形；而且 F1(n-1) 虽然规模在缩小，但没有终止条件，会一直减到负数、继续减下去，直到栈溢出。
• (b) 违反条件 ②（规模缩减）。 基准情形 n == 0 写对了，但 F2(n + 1) 让 $n$ 越来越大，永远到不了 0 —— 除非传入负数，那时会立刻返回。这类 bug 的特点是"在某个特定输入下看起来正常"，更隐蔽。
• (c) 这个函数其实是对的，但要有前提。 F3 的规模确实在缩小（$n/2$ 和 $n/3$ 都小于 $n$），最终会缩到 0。 前提是 n 是非负整数。如果是负数，C# 的整数除法会向零取整（-1 / 2 == 0），也能停；但如果一开始就传 0 之外的小数就不成立了。这类"规模确实在缩小但缩得很慢"的递归，要额外关注它的递归深度（见 2.2 节）。

2.1.3

static void CountDown(int n)
{
    if (n == 0)                 // 基准情形：数到 0 就停
    {
        Console.WriteLine("发射！");
        return;
    }
    Console.WriteLine(n);       // 先打印自己
    CountDown(n - 1);           // 再交给下一层
}

输出：

3
2
1
发射！

关键点：Console.WriteLine(n) 写在递归调用之前，所以是"去程打印"，顺序是从大到小。 如果把这两行调换（先递归再打印），输出会变成从小到大 —— 这正是下一题要考察的。

2.1.4

输出：

3
2
1
1
2
3

推演过程：

• 去程依次打印 3、2、1（位置 A，在递归调用之前）
• 撞上基准情形 n == 0，直接返回
• 回程依次打印 1、2、3（位置 B，在递归调用之后）

把 A 和 B 交换当然会变 —— 那就变成了全部在回程打印，输出会是 1 2 3 3 2 1（顺序反过来：先最内层打印）。

这就是判断"去程还是回程"的通用方法： 写在递归调用之前的语句，在去程执行（由外向内）；写在调用之后的语句，在回程执行（由内向外）。

树的三种遍历顺序（前序、中序、后序，见 9.2 节）就是靠这个规律区分的 —— 它们唯一的差别就是"打印"这一行放在两次递归调用的哪个位置。

2.1.5

• (a) $n + 1$ 个。 从 i=0 一直到 i=n（下标等于长度的那次是基准情形），一共 $n+1$ 次调用。
• (b) $n + 1$ 个同时活着。 去程最深的那一刻，从 Sum(i=0) 到 Sum(i=n) 全都没有返回，全部占据着内存。这就是递归的空间代价。
• (c) 不能跑，会栈溢出崩溃。 100 万个调用同时活着需要的栈空间远超线程默认的 1 MB。 实测数据见 2.2 节：本机环境下大约 1.6 万层就溢出了。所以在真实工程中，递归深度超过几千就要警惕，超过几万基本必崩。

三个数据的量级对比值得记住：$n = 1{,}000{,}000$ 的元素，用循环只需要 1 份状态；用递归需要 100 万份。 这就是 2.3 节要学改写的原因。

八、常见错误

九、本节总结

1. 递归必须同时满足两个条件：有基准情形（什么时候停）+ 规模严格缩减（每次更靠近停）。
2. 递归分去程和回程：去程一路调用到基准情形，回程才真正算出结果。写在递归调用前/后的语句，分别在两程执行。
3. 递归的空间代价 = 同时活着的调用数量 = 递归深度。循环只有 1 份状态，递归有 $n$ 份。
4. 递归写法简洁，但简洁不等于快：Fib(35) 的朴素递归要调用 2986 万次。
5. 判断去程/回程的规律，将在 9.2 节用来一次性搞懂二叉树的前序、中序、后序遍历。

下一节衔接：本节反复提到"同时活着的调用"和"栈溢出"，但一直没说清楚这些调用到底存在哪儿、为什么会崩。下一节把调用栈这层窗户纸捅破 —— 并且会让你亲眼看到程序崩溃的样子（放心，这是故意的）。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "2.1",
  "title": "递归的两个必要条件",
  "covered": [
    "递归的白话定义与电影院类比",
    "基准情形与规模缩减两个必要条件（含两个反例）",
    "递归求和的完整调用过程追踪（去程/回程可视化）",
    "阶乘、字符串反转的递归实现",
    "朴素斐波那契的调用次数实测（21891 → 29860703）",
    "「调用之前的语句在去程执行」这条通用规律"
  ],
  "unresolved": [
    "调用栈与栈溢出的机制留到 2.2",
    "记忆化与 DP 留到 15.1",
    "树的三种遍历顺序留到 9.2"
  ],
  "canonical_terms": {
    "递归": "函数直接或间接调用自身来解决问题",
    "基准情形": "递归中不再调用自身的终止条件",
    "递归情形": "递归中把问题缩小后再次调用的部分"
  },
  "symbols_units": {},
  "assumptions": [
    "读者会写方法、if 分支",
    "读者对「数组」按下标访问已经熟悉"
  ],
  "word_count_actual": 1720,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch02/Sec21/",
    "斐波那契调用次数为经典值，已与实测逐项核对：21891 / 242785 / 2692537 / 29860703",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "next": "2.2 调用栈：递归的代价与深度限制"
}