GESP5级C++考试语法知识（十二、递归算法（二））

🌟 第一章：递归复杂度如何计算（“分身术小精灵”）

1、🎯 故事：

递归小精灵有一个技能：

👉可以“分身”去解决子问题！

2、但问题来了：

• 有的精灵：只分出1个分身 😌

• 有的精灵：分出2个 😮

• 有的精灵：分出3个甚至更多 😱

3、👉 分身越多，工作量就会爆炸增长！

🌟 第二章：递归复杂度的核心公式

1、判断递归复杂度，最关键看这个：

T(n) = a * T(n/b) + f(n)

2、👉 这是经典模型（分治思想）

3、🧠 各个参数含义：

4、👉 简单记：

💡“分几叉（a） + 深度多少（log n）”

🌟 第三章：三种经典递归类型对比🔥

🎯 类型1：一条链（最简单）

1、示例：求阶乘

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

2、🌲 递归树

f(n) ↓ f(n-1) ↓ f(n-2) ↓ ...

3、🧠 分析：

• 每次只调用 1 个子问题 👉 a = 1

• 深度：n

👉 总次数：

O(n)

4、🎯 结论：

👉单链递归 = O(n)

🎯 类型2：二叉爆炸（很危险🔥）

1、示例：斐波那契

int f(int n) { if(n <= 2) return 1; return f(n-1) + f(n-2); }

2、🌲 递归树

f(n) / \ f(n-1) f(n-2) / \ ...

3、🧠 分析：

• 每次分成 2 个 👉 a = 2

• 深度：n

👉 节点数 ≈

O(2^n)

💥 指数爆炸！

4、🎯 结论：

👉多叉递归 + 无优化 = 指数复杂度

🎯 类型3：分治递归（高效）

1、示例：归并排序

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

2、🌲 递归树（关键！）

层1: n 层2: n 层3: n ...

👉 每一层工作量都是 n！

3、🧠 分析：

• 分成2个问题 👉 a = 2

• 每个规模 n/2 👉 b = 2

• 层数：log n

• 每层：O(n)

👉 总：

O(n log n)

🌟 第四章：为什么差距这么大？

1、🎯 核心原因：

👉有没有“重复计算”！

2、❌ 斐波那契：

• f(3) 被算很多次 ❌

• 浪费大量时间 ❌

👉 指数级

3、✅ 归并排序：

• 每个子问题只算一次 ✅

• 没有重复 ✅

👉 n log n

🌟 第五章：万能判断方法（考试必会🔥）

🎯 方法1：画递归树（最推荐）

步骤：

1️⃣ 看分几叉（a）

• 1个 👉 线性

• 2个 👉 小心爆炸

2️⃣ 看深度

• 每次减1 👉 深度 n

• 每次减半 👉 深度 log n

3️⃣ 估算总节点数

🎯 快速口诀：

链式 → O(n) 二叉爆炸 → O(2^n) 分治 → O(n log n)

🎯 方法2：看是否有重复子问题

1、👉 问自己：

❓ “这个子问题会不会被重复算？”

2、判断：

🎯 方法3：看是否可以记忆化

👉 如果可以记忆化：

👉 复杂度通常可以优化为：

指数 → 线性

🌟 第六章：几个经典对比🔥

1、🎯 对比1：斐波那契

2、🎯 对比2：DFS搜索

（1）👉 最坏：

O(分支数^深度)

（2）比如：

• 每步4个方向

• 走10步

（3）👉

O(4^10)

🌟 第七章：一眼判断技巧（非常重要🔥）

🎯 快速判断表

🌟 最终总结

1、🎯 本质一句话：

👉递归复杂度 = 分支数 × 深度

2、🎯 更精准一点：

👉递归树节点总数

3、🎯 最重要的判断：

有没有重复计算？！

接下来，我们进行🌟《递归王国闯关大冒险》🌟

🏰 第1关：小兔子爬楼梯（基础递归）

1、🎯 故事

小兔子要跳到第 n 阶楼梯
每次可以跳 1 阶 或 2 阶

👉 问：一共有多少种跳法？

2、🧠 思路（递归）

（1）第 n 阶的方法：

• 从 n-1 跳一步

• 从 n-2 跳两步

（2）👉 所以：

f(n) = f(n-1) + f(n-2)

3、✅ C++代码

#include <iostream> using namespace std; int f(int n) { if(n == 1) return 1; if(n == 2) return 2; return f(n-1) + f(n-2); } int main() { int n; cin >> n; cout << f(n); }

4、⏱ 时间复杂度

👉 每次分成 2 个递归！

像一棵树：

f(n) / \ f(n-1) f(n-2) / \ / \ ...

👉 节点数 ≈ 2^n

✅时间复杂度：O(2^n)（指数爆炸💥）

5、🧠 空间复杂度

👉 最深一路：n → n-1 → n-2 → ... → 1

✅空间复杂度：O(n)

🏰 第2关：数字拆分（打印每一位）

1、🎯 故事

魔法数字 1234 被锁住了
需要一位一位从高到低念出来！

2、🧠 思路

递归思路：

👉 先处理前面，再处理最后一位

print(n/10) 输出 n%10

3、✅ C++代码

#include <iostream> using namespace std; void print(int n) { if(n == 0) return; print(n / 10); cout << n % 10 << " "; } int main() { int n; cin >> n; print(n); }

4、⏱ 时间复杂度

（1）👉 每次去掉一位

比如：

1234 → 123 → 12 → 1

👉 共 d 次（位数）

（2）✅时间复杂度：O(d)
👉 d ≈ log₁₀(n)

👉 所以：

✅O(log n)

5、🧠 空间复杂度

👉 递归深度 = 位数

✅O(log n)

🏰 第3关：阶乘魔法

1、🎯 故事

魔法师说：

n! = n × (n-1)!

2、🧠 思路

递归公式：

f(n) = n * f(n-1)

边界：

f(1) = 1

3、✅ C++代码

#include <iostream> using namespace std; int f(int n) { if(n == 1) return 1; return n * f(n-1); } int main() { int n; cin >> n; cout << f(n); }

4、⏱ 时间复杂度

（1）👉 每次只调用 1 次

n → n-1 → n-2 → ... → 1

（2）👉 共 n 次

✅时间复杂度：O(n)

5、🧠 空间复杂度

👉 深度 = n

✅O(n)

🏰 第4关：字符串反转

1、🎯 故事

（1）一段咒语：

HELLO

（2）需要倒着念：

OLLEH

2、🧠 思路

👉 先递归后面的，再输出当前字符

3、✅ C++代码

#include <iostream> using namespace std; void rev(string s, int i) { if(i == s.size()) return; rev(s, i + 1); cout << s[i]; } int main() { string s; cin >> s; rev(s, 0); }

4、⏱ 时间复杂度

👉 每个字符访问一次

字符串长度 = n

✅时间复杂度：O(n)

5、🧠 空间复杂度

👉 递归深度 = n

✅O(n)

🏰 第5关：汉诺塔（经典递归🔥）

1、🎯 故事

3根柱子，要把盘子从 A 移到 C

规则：

• 每次只能移动一个

• 大的不能压小的

2、🧠 思路

核心递归：

1️⃣ 把 n-1 从 A → B
2️⃣ 把第 n 个 A → C
3️⃣ 把 n-1 从 B → C

3、✅ C++代码

#include <iostream> using namespace std; void hanoi(int n, char A, char B, char C) { if(n == 1) { cout << A << "->" << C << endl; return; } hanoi(n-1, A, C, B); cout << A << "->" << C << endl; hanoi(n-1, B, A, C); } int main() { int n; cin >> n; hanoi(n, 'A', 'B', 'C'); }

4、⏱ 时间复杂度

（1）递推式：

T(n) = 2*T(n-1) + 1

（2）展开：

T(n) = 2^n - 1

（3）✅时间复杂度：O(2^n)

👉 超级费时间！

5、🧠 空间复杂度

👉 最大深度 = n

✅O(n)

🏰 第6关：斐波那契（递归效率陷阱）

1、🎯 故事

兔子繁殖：

1 1 2 3 5 8 ...

2、🧠 思路

f(n) = f(n-1) + f(n-2)

⚠️ 会重复计算！

3、✅ 递归版本（慢）

int f(int n) { if(n <= 2) return 1; return f(n-1) + f(n-2); }

4、🚀 优化（记忆化）

#include <iostream> using namespace std; int dp[1000]; int f(int n) { if(n <= 2) return 1; if(dp[n]) return dp[n]; return dp[n] = f(n-1) + f(n-2); } int main() { int n; cin >> n; cout << f(n); }

5、❌ 普通递归

⏱ 时间复杂度

同第1关：

✅O(2^n)

6、🚀 记忆化版本

👉 每个 f(n) 只算一次！

⏱ 时间复杂度

👉 一共 n 个状态

✅O(n)

7、🧠 空间复杂度

👉 dp数组 + 递归深度

✅O(n)

🎉 总结

这 6 关在训练你：