【GESP】C++五级考试大纲知识点梳理, (7) 递归算法 -2 复杂度分析

GESP C++五级官方考试大纲中，共有9条考点，本文针对第7条考点进行分析介绍。

（7）掌握递归算法的基本原理，能够应用递归解决问题，能够分析递归算法的时间复杂度和空间复杂度，了解递归的优化策略。

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

五级其他考点回顾：

• 【GESP】C++五级考试大纲知识点梳理, (1) 初等数论
• 【GESP】C++五级考试大纲知识点梳理, (2) 模拟高精度计算
• 【GESP】C++五级考试大纲知识点梳理, (3-1) 链表-单链表
• 【GESP】C++五级考试大纲知识点梳理, (3-2) 链表-双向链表
• 【GESP】C++五级考试大纲知识点梳理, (3-3) 链表-单向循环链表
• 【GESP】C++五级考试大纲知识点梳理, (3-4) 链表-双向循环链表
• 【GESP】C++五级考试大纲知识点梳理, (4) 辗转相除法、素数表和唯一性定理
• 【GESP】C++五级考试大纲知识点梳理, (5) 算法复杂度估算（多项式、对数）
• 【GESP】C++五级考试大纲知识点梳理, (6) 二分查找和二分答案
• 【GESP】C++五级考试大纲知识点梳理, (7) 递归算法 - 1 基本原理

---

在梳理的过程中，我发现想尽可能说清楚考纲要求的内容，越总结篇幅越长，为了避免总结遗漏和阅读匹配，我计算分三次介绍本部分内容，即：

1. 递归算法基本原理和常见形式
2. 递归算法时间、空间复杂度分析
3. 递归算法优化策略

本次为第二部分介绍。

递归算法因代码简洁、逻辑直观，成为解决分治、回溯类问题的常用工具，但“层层调用”的特性也让其时间复杂度分析比迭代算法更复杂。

---

一、时间复杂度分析

1.1 递归时间复杂度分析的本质：看调用次数 × 每次工作量

递归算法的运行时间，取决于递归调用的次数和每次调用要干的活。

换句话说，我们要搞清楚：

• 递归函数会被调用多少次？
• 每次调用花多长时间？

只要能回答这两个问题，复杂度就能算出来。

---

1.2 三步通用分析法

我们通常用下面 三步法 来分析递归复杂度：

第 1 步：写出递归式

假设递归问题规模是 n，那么写出： \(T(n) = a \times T(n/b) + f(n)\) 意思是：

• 把问题拆成 $a$ 个 子问题；
• 每个子问题规模是原来的 $n/b$；
• 拆分和合并需要 $f(n)$ 的时间。

第 2 步：分析子问题的增长规律

看递归树怎么展开，越往下子问题越多、越小。

第 3 步：求出总和（用递归树法或主定理）

算出整棵递归树所有节点的总工作量。下面分别介绍这两种方法。

---

1.3 递归树法（最直观的理解方式）

递归树法其实就是「画一棵树」来看递归展开过程，例如：👇

示例 1：二分查找

// 二分查找：在有序数组 arr[left...right] 中查找目标值 target
int binarySearch(int arr[], int left, int right, int target) {
    // 如果区间无效，说明未找到，返回 -1
    if (left > right) {
        return -1;
    }
    int mid = (left + right) / 2; // 计算中间位置
    if (arr[mid] == target) {
        return mid; // 找到目标，返回下标
    } else if (arr[mid] > target) {
        // 目标在左半部分，递归查找左区间
        return binarySearch(arr, left, mid - 1, target);
    } else {
        // 目标在右半部分，递归查找右区间
        return binarySearch(arr, mid + 1, right, target);
    }
}

分析：

• 每次只递归一次（$a = 1$）
• 规模减半（$b = 2$）
• 其他操作 $O(1)$

写出递归式： \(T(n) = T(n/2) + O(1)\)

画成树后你会发现，深度是 $\log_2n$，每层只干一点活： \(T(n) = O(\log n)\)

---

示例 2：归并排序

void mergeSort(int arr[], int l, int r) {
    // 区间长度 ≤ 1 时已经有序，直接返回
    if (l >= r) {
        return;
    }
    // 取中点，将区间一分为二
    int mid = (l + r) / 2;
    // 递归排序左半部分 [l, mid]
    mergeSort(arr, l, mid);
    // 递归排序右半部分 [mid+1, r]
    mergeSort(arr, mid + 1, r);
    // 合并两个已排序的子区间
    merge(arr, l, mid, r);
}

分析：

• 拆成两个子问题（$a = 2$）
• 每个子问题规模一半（$b = 2$）
• 合并需要 $O(n)$ 时间

递归式： \(T(n) = 2T(n/2) + O(n)\)

画成树：

• 第 0 层：1 个节点，工作量 $n$
• 第 1 层：2 个节点，总工作量 $n$
• 第 2 层：4 个节点，总工作量 $n$
• ……
• 一共有 $O(\log_2 n)$ 层

总时间： \(T(n) = O(n \log n)\)

---

1.4 主定理（Master Theorem）

当我们懒得画树时，可以直接用主定理。

对于递归式： \(T(n) = aT(n/b) + f(n)\) 主定理告诉我们：

情况	规律	复杂度
1️⃣ 子问题主导	若 $f(n) = O(n^{\log_b a - \epsilon})$	$T(n) = \Theta(n^{\log_b a})$
2️⃣ 平衡	若 $f(n) = \Theta(n^{\log_b a})$	$T(n) = \Theta(n^{\log_b a} \log n)$
3️⃣ 合并主导	若 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 且满足正则性条件*	$T(n) = \Theta(f(n))$

注：正则性条件说明

正则性条件：存在常数 $c<1$ 使得对所有足够大的 $n$ 有 $a f(n/b) \le c f(n)$，确保“上层合并不吃掉下层优势”。

举几个典型例子：

递归式	主定理判定过程	复杂度	例子
$T(n) = 2T(n/2) + O(n)$	$n^{\log_b a}=n^1$，$f(n)=O(n)$ 恰好相等 → 情况2️⃣ 平衡	$O(n \log n)$	归并排序
$T(n) = T(n/2) + O(1)$	$n^{\log_b a}=n^0=1$，$f(n)=O(1)$ 恰好相等 → 情况2️⃣ 平衡	$O(\log n)$	二分查找
$T(n) = 4T(n/2) + O(n^2)$	$n^{\log_b a}=n^2$，$f(n)=O(n^2)$ 恰好相等 → 情况2️⃣ 平衡	$O(n^2 \log n)$	四分递归（例如图像分割）
$T(n) = 9T(n/3) + O(n)$	$n^{\log_b a}=n^2$，$f(n)=O(n)=O(n^{2-1})$ 多项式小于 → 情况1️⃣ 子问题主导	$O(n^2)$	分治矩阵乘法（朴素法）
$T(n) = 2T(n/2) + O(n^2)$	$n^{\log_b a}=n^1$，$f(n)=O(n^2)$ 多项式大于 → 情况3️⃣ 合并主导	$O(n^2)$	暴力合并的区间问题

---

1.5 小结

技巧/误区	说明
✅ 常数项不影响复杂度	只看数量级
✅ 画递归树最直观	适合新手理解结构
⚠️ 不要只看递归次数	每层的「工作量」常常不同
⚠️ 要区分尾递归和非尾递归	尾递归能优化空间，但不改变时间复杂度

---

二、空间复杂度分析

空间复杂度描述的是：

算法在运行过程中额外占用的内存空间量，与输入规模 $n$ 的关系。

“额外”指的是不算输入数据本身，只算程序执行中自己用到的额外内存，例如：

• 临时变量；
• 函数调用栈；
• 临时数组或缓冲区。

---

1.1 递归为什么会占用空间

因为每一次函数调用，计算机都会在调用栈（call stack）里存放一份当前函数的信息：

• 参数值；
• 局部变量；
• 返回地址。

当函数自己调用自己时，会再压入一层栈帧。

比如你写：

void f(int n) {
    if (n == 0) return;
    f(n - 1);
}

每次 f(n) 调用 f(n-1) 时，系统会新建一个“函数栈帧”。 直到递归到底（n==0）才开始弹栈。

所以：

• 栈的深度 = 递归的层数；
• 每一层栈帧占一定空间；

因此：

递归的空间复杂度 = 递归调用的最大深度 × 每次调用占用的空间。

通常，每次调用的局部变量数量是常数级的，所以空间复杂度主要看递归深度。

---

1.2 举例子分析

例1：简单线性递归

void f(int n) {
    if (n == 0) return;
    f(n - 1);
}

• 最大调用深度：$n$
• 每次只用常数空间（比如局部变量 $n$）

✅ 空间复杂度：$O(n)$

---

例2：二叉递归

void f(int n) {
    if (n == 0) return;
    f(n - 1);
    f(n - 1);
}

你可能以为是 $O(2^n)$，其实不是！

空间不是时间。 虽然函数被调用了很多次，但它们不是同时存在的，因为每次左子递归返回后，才开始右子递归。

• 递归深度仍是 $n$；
• 所以栈深度也就是 $n$ 层

✅ 空间复杂度仍是 $O(n)$。

---

例3：分治算法（如归并排序）

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    merge(l, mid, r); // 合并
}

• 递归深度是 $O(\log n)$（每次一分为二）。
• 但合并时可能用一个临时数组来存结果，这个临时数组大小为 $O(n)$。

所以：

• 栈空间：$O(\log n)$
• 额外数组：$O(n)$

✅ 总空间复杂度：$O(n)$（取最大者）

---

例4：尾递归优化（特殊情况）

void tail(int n, int acc) {
    if (n == 0) return;
    tail(n - 1, acc + n);
}

如果编译器支持尾递归优化（TCO）， 系统就不会真的创建新的栈帧，而是重用当前函数的空间。 ✅ 空间复杂度从 $O(n)$ 降到 $O(1)$。

（但 C++ 默认不保证 TCO，一般仍是 $O(n)$）

---

1.3 小结

1️⃣ 确定递归的最大深度（最深能调用多少层）。
2️⃣ 看每层使用了多少局部空间（常量？数组？）。
3️⃣ 判断是否有额外辅助结构（比如合并时的临时数组）。
4️⃣ 计算总空间 = 栈空间 + 辅助空间。
5️⃣ 忽略常数项，取最大阶，写成 O(·) 表达。

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号