课程进度 75% · 第8/10章第8/10章 · 标签 1/2
— 1 —
递归思想与写法
递归是函数直接或间接调用自身，常用于分解重复子问题。递归与迭代的区别在于递归用栈保存状态，迭代用循环。递归模板：
cpp
1
// 递归模板
2
void recur(参数) {
3
if (终止条件) return;
4
// 处理当前层逻辑
5
recur(子问题参数);
6
// （可选）回溯清理
7
}
示例：斐波那契数列（递归与迭代）
cpp
1
// 递归写法
2
int fib(int n) {
3
if (n <= 1) return n;
4
return fib(n - 1) + fib(n - 2);
5
}
6
// 迭代写法
7
int fibIter(int n) {
8
if (n <= 1) return n;
9
int a = 0, b = 1;
10
for (int i = 2; i <= n; ++i) {
11
int c = a + b; a = b; b = c;
12
}
13
return b;
14
}
— 2 —
分治算法与典型问题
分治法将大问题分解为小问题递归求解，典型如归并排序、快速排序、二分查找、最近点对等：
cpp
1
// 归并排序（分治）
2
void mergeSort(vector<int>& a, int l, int r) {
3
if (l >= r) return;
4
int m = l + (r - l) / 2;
5
mergeSort(a, l, m);
6
mergeSort(a, m + 1, r);
7
merge(a, l, m, r);
8
}
cpp
1
// 二分查找（分治）
2
int binarySearch(vector<int>& a, int l, int r, int x) {
3
if (l > r) return -1;
4
int m = l + (r - l) / 2;
5
if (a[m] == x) return m;
6
else if (a[m] < x) return binarySearch(a, m + 1, r, x);
7
else return binarySearch(a, l, m - 1, x);
8
}
递归分治斐波那契迭代回溯