一、递归（Recursion）
1. 概念
函数自己调用自己，把大问题拆成更小的同类型问题。
2. 两个必备条件
- 递归出口（base case）：不再递归，直接返回结果
- 递归式：把问题规模缩小
3. 经典示例：求阶乘
1 2 3 4 |
|
4. 本质
- 系统使用栈保存每一层调用
- 太深会栈溢出（stack overflow）
二、搜索（Search）
搜索就是在所有可能情况里找答案。常见两类：
- 深度优先搜索 DFS（一条路走到底）
- 广度优先搜索 BFS（一层层扩散）
递归最常配合DFS。
三、回溯（Backtracking）
1. 概念
递归搜索 + 撤销选择= 回溯
- 选一条路走
- 走不通就回退一步
- 尝试其他可能
典型场景：排列、组合、子集、N 皇后、数独
2. 回溯通用模板（必背）
1 2 3 4 5 6 7 8 9 10 11 |
|
四、三个经典例子（一看就懂）
例 1：全排列（回溯经典）
求[1,2,3]的所有排列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
例 2：子集（搜索所有可能）
1 2 3 4 5 6 7 8 |
|
例 3：斐波那契（纯递归）
1 2 3 4 |
|
五、三者关系（一句话总结）
- 递归：函数自己调用自己，是实现方式
- 搜索：遍历所有可能，是算法思想
- 回溯：递归搜索 + 撤销选择，是搜索的一种通用写法
六、最常考题型
- 全排列、组合、子集
- N 皇后
- 数独
- 电话号码字母组合
- 矩阵中的路径（单词搜索）
- 分割回文串
到此这篇关于C++ 递归、搜索与回溯的文章就介绍到这了,
