第十五章：递归算法——函数调用自己¶
你好！欢迎来到第十五章！在前面的章节，我们学习了递推，从已知条件一步步推出结果。这一章我们学习另一种重要的思想：递归——函数自己调用自己。就像俄罗斯套娃，一个大娃娃里面套着一个一模一样的小娃娃。递归在解决某些问题时特别简洁，比如遍历文件夹、计算阶乘、汉诺塔等。让我们一起来探索递归的奥秘吧！
15.1 递归算法程序范例¶
先来看一个最简单的递归例子：计算阶乘 n!。阶乘的定义是：
- n! = 1 × 2 × 3 × … × n
- 也可以用递归定义：n! = n × (n-1)!，且 0! = 1。
#include <iostream>
using namespace std;
// 递归函数求阶乘
int factorial(int n) {
if (n == 0) { // 递归终止条件
return 1;
} else {
return n * factorial(n - 1); // 递归调用
}
}
int main() {
int n;
cout << "请输入一个整数：";
cin >> n;
cout << n << "! = " << factorial(n) << endl;
return 0;
}
运行示例（输入5）：
5! = 120
这个程序里，factorial 函数在计算过程中又调用了自己，这就是递归。但递归不能无限进行下去，必须有一个终止条件（这里 n == 0 时返回1），否则就会陷入死循环（最终栈溢出）。
15.2 递归算法的用法¶
15.2.1 什么是递归？¶
递归就是一个函数直接或间接地调用自身。递归可以把一个复杂问题分解成与原问题相似但规模更小的子问题，直到子问题简单到可以直接求解（终止条件）。
生活中的递归例子：
- 俄罗斯套娃：打开一个娃娃，里面是一个更小的娃娃，直到最小的那个。
- 查字典：要查一个词，发现解释里用了另一个词，又去查那个词，直到某个词的解释简单易懂。
15.2.2 递归的要素¶
- 递归终止条件（基线条件）：问题规模足够小，可以直接得到答案，不再调用自身。
- 递归关系（递归步骤）：将原问题转化为规模更小的子问题，并调用自身解决子问题，然后组合结果。
15.2.3 递归的执行过程¶
以 factorial(3) 为例：
- 调用 factorial(3) → 3 != 0，执行 3 * factorial(2)
- 调用 factorial(2) → 2 != 0，执行 2 * factorial(1)
- 调用 factorial(1) → 1 != 0，执行 1 * factorial(0)
- 调用 factorial(0) → 0 == 0，返回 1
- 回到 factorial(1)，得到 11 = 1，返回
- 回到 factorial(2)，得到 21 = 2，返回
- 回到 factorial(3)，得到 3*2 = 6，返回
这个过程像一层层深入，再一层层返回，所以递归需要系统栈来保存每一层的局部变量和返回地址。
15.2.4 递归与循环的比较¶
| 特点 | 递归 | 循环 |
|---|---|---|
| 代码简洁性 | 通常更简洁，符合数学定义 | 可能需要更多代码 |
| 可读性 | 对某些问题很直观 | 通用 |
| 效率 | 有函数调用开销，可能重复计算 | 通常更快 |
| 栈溢出风险 | 层次太深会栈溢出 | 无此问题 |
| 适用问题 | 树、图、分治等 | 线性重复 |
注意：能用循环解决的问题尽量用循环，但有些问题（如汉诺塔、树的遍历）用递归更自然。
15.2.5 递归的注意事项¶
- 必须有终止条件，否则无限递归导致程序崩溃。
- 递归层次不能太深，否则会栈溢出（系统栈空间有限，一般几千层）。
- 避免重复计算：比如递归求斐波那契数会有大量重复，可以用记忆化（备忘录）优化。
15.3 编程实例讲解¶
实例1：递归求斐波那契数列（简单版，可能有重复计算）¶
#include <iostream>
using namespace std;
int fib(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fib(n - 1) + fib(n - 2); // 大量重复
}
}
int main() {
int n;
cout << "请输入n：";
cin >> n;
cout << "第" << n << "项是：" << fib(n) << endl;
return 0;
}
问题：n=40 时就会非常慢，因为重复计算太多。可以用记忆化优化。
实例2：记忆化递归（备忘录）¶
用一个数组保存已经算过的值，避免重复计算。
#include <iostream>
using namespace std;
const int N = 100;
long long memo[N] = {0}; // 记忆数组，初始0表示未计算
long long fib(int n) {
if (n == 1 || n == 2) return 1;
if (memo[n] != 0) return memo[n]; // 直接返回已计算结果
memo[n] = fib(n - 1) + fib(n - 2); // 计算并保存
return memo[n];
}
int main() {
int n;
cout << "请输入n：";
cin >> n;
cout << "第" << n << "项是：" << fib(n) << endl;
return 0;
}
实例3：汉诺塔问题¶
题目：有三根柱子A、B、C，A柱上有n个大小不同的圆盘，大盘在下小盘在上。要求把所有圆盘从A移到C，每次只能移动一个，且小盘不能压在大盘上。输出移动步骤。
递归思路：
- 要把n个盘子从A移到C，可以先把上面n-1个盘子从A移到B（借助C），然后把最大的盘子从A移到C，最后把n-1个盘子从B移到C（借助A）。
#include <iostream>
using namespace std;
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
cout << "移动盘子 1 从 " << from << " 到 " << to << endl;
return;
}
hanoi(n - 1, from, aux, to); // 把上面n-1个从from移到aux
cout << "移动盘子 " << n << " 从 " << from << " 到 " << to << endl;
hanoi(n - 1, aux, to, from); // 把n-1个从aux移到to
}
int main() {
int n;
cout << "请输入盘子数：";
cin >> n;
hanoi(n, 'A', 'C', 'B');
return 0;
}
运行示例（n=3）：
移动盘子 1 从 A 到 C
移动盘子 2 从 A 到 B
移动盘子 1 从 C 到 B
移动盘子 3 从 A 到 C
移动盘子 1 从 B 到 A
移动盘子 2 从 B 到 C
移动盘子 1 从 A 到 C
实例4：递归遍历文件夹（伪代码，需要用到系统函数）¶
虽然不能直接运行，但可以展示思想：遍历文件夹时，如果是文件就处理，如果是文件夹就递归进入。
#include <iostream>
#include <filesystem> // C++17 需要
namespace fs = std::filesystem;
void listFiles(const fs::path &path) {
for (const auto &entry : fs::directory_iterator(path)) {
if (entry.is_directory()) {
listFiles(entry.path()); // 递归子文件夹
} else {
cout << entry.path() << endl;
}
}
}
实例5：递归求最大公约数（辗转相除法）¶
辗转相除法的递归定义：gcd(a, b) = gcd(b, a % b)，直到 b=0。
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
实例6：全排列生成¶
用递归生成一个数组的所有排列（经典回溯）。
#include <iostream>
using namespace std;
void permute(int arr[], int l, int r) {
if (l == r) {
for (int i = 0; i <= r; i++) cout << arr[i] << " ";
cout << endl;
} else {
for (int i = l; i <= r; i++) {
swap(arr[l], arr[i]);
permute(arr, l + 1, r);
swap(arr[l], arr[i]); // 回溯
}
}
}
int main() {
int arr[] = {1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
permute(arr, 0, n - 1);
return 0;
}
15.4 阶段性编程练习¶
- 练习1：用递归求 1+2+…+n 的和。
- 练习2：用递归判断一个字符串是否是回文（如 “abcba”）。
- 练习3：用递归实现二分查找（在有序数组中找某个数）。
- 练习4：用递归输出杨辉三角的第n行（提示：杨辉三角可以用递归公式 C(n,k) = C(n-1,k-1) + C(n-1,k)）。
- 练习5：用递归解决“数字反转”问题（输入一个整数，输出反转后的数，如 1234 → 4321，考虑负数？）
15.5 第15章编程作业¶
作业1：递归求幂¶
写一个递归函数 double power(double x, int n) 计算 x 的 n 次幂（n 为非负整数）。要求时间复杂度 O(n)。
作业2：猴子吃桃（递归版）¶
猴子第一天摘了若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天又将剩下的桃子吃了一半，又多吃了一个。以后每天都这样。到第10天早上想再吃时，只剩一个桃子了。用递归函数求第一天摘了多少个桃子。
作业3：整数划分¶
将一个正整数 n 划分成若干个正整数之和，求划分的种数。例如 n=4 有 5 种划分：4, 3+1, 2+2, 2+1+1, 1+1+1+1。用递归实现。
作业4：汉诺塔步数计算¶
在汉诺塔问题中，移动 n 个盘子需要多少步？推导出公式并用递归验证。
作业5：八皇后问题（选做）¶
在 8×8 的国际象棋棋盘上放置八个皇后，使得它们互不攻击（即任意两个不在同一行、同一列、同一对角线上）。用递归回溯法求解并输出所有解（或一个解）。
恭喜你完成了第十五章的学习！递归是一种强大的编程思想，它让我们能简洁地解决许多复杂问题。虽然递归有时效率不高，但它的思维方式非常重要，也是学习更高级算法（如动态规划、回溯、分治）的基础。加油！🚀