递归 Recursion
- 函数自身调用自身
- 通过函数体来进行的循环
- 以自相似的方法重复进行的过程
- 递归的三个关键
定义需要递归的问题（重叠子问题）- 数学归纳法思维确定递归边界保护与还原现场
| 递归形式 | 时间复杂度规模 | 问题举例 |
|---|---|---|
| 指数型 | 2 n 2^n 2n | 子集 |
| 排列型 | n ! n! n! | 全排列 |
| 组合型 | ( n m ) = n ! m ! ( n − m ) ! \binom{n}{m} = \frac{n!}{m!(n-m)!} (mn)=m!(n−m)!n! | 组合选数 |
void recursion(int level, int param) {
// terminator
if (level > MAX_LEVEL) {
// process result
return;
}
// process logic in current level
process(level, param);
// drill down
recur(level + 1, new_param);
// restore the current level status
}
// 计算 n! = 1 * 2 * 3 * ... * n
int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
LeetCode 练习题
- 78. 子集
- 77. 组合
- 46. 全排列
- 47. 全排列 II
分治
- 把原问题划分成若干个同类子问题，分别解决后，再把结果合并起来
- 原问题和各个子问题都是重复的（同类的）
- 除了向下递归 “问题”，还要向上合并 “结果”
- 分治算法一般用递归实现
LeetCode 练习题
- 50. Pow(x, n)
- 22. 括号生成
- 23. 合并 K 个升序链表
