C++ 递归、搜索与回溯:三剑客

下面用最清晰、最容易理解的方式，一次性讲透 C++ 递归、搜索、回溯三大核心内容，适合学习、复习、写题。

一、递归（Recursion）

1. 概念

函数自己调用自己，把大问题拆成更小的同类型问题。

2. 两个必备条件

1. 递归出口（base case）：不再递归，直接返回结果
2. 递归式：把问题规模缩小

3. 经典示例：求阶乘

int fact(int n) {
    if (n == 0) return 1;       // 出口
    return n * fact(n - 1);     // 递归式
}

4. 本质

• 系统使用栈保存每一层调用
• 太深会栈溢出（stack overflow）

二、搜索（Search）

搜索就是在所有可能情况里找答案。常见两类：

1. 深度优先搜索 DFS（一条路走到底）
2. 广度优先搜索 BFS（一层层扩散）

递归最常配合 DFS。

三、回溯（Backtracking）

1. 概念

递归搜索 + 撤销选择 = 回溯

• 选一条路走
• 走不通就回退一步
• 尝试其他可能

典型场景：排列、组合、子集、N 皇后、数独

2. 回溯通用模板（必背）

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        记录答案;
        return;
    }
    for (选择 : 选择列表) {
        做选择;
        backtrack(路径, 选择列表);
        撤销选择;   // 回溯核心
    }
}

四、三个经典例子（一看就懂）

例 1：全排列（回溯经典）

求 [1,2,3] 的所有排列

vector<vector<int>> res;
vector<int> path;
bool vis[10];
void dfs(vector<int>& nums) {
    if (path.size() == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (vis[i]) continue;
        vis[i] = 1;
        path.push_back(nums[i]);
        dfs(nums);
        path.pop_back();   // 回溯
        vis[i] = 0;
    }
}

例 2：子集（搜索所有可能）

void dfs(vector<int>& nums, int u) {
    res.push_back(path);
    for (int i = u; i < nums.size(); i++) {
        path.push_back(nums[i]);
        dfs(nums, i + 1);
        path.pop_back();
    }
}

例 3：斐波那契（纯递归）

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

五、三者关系（一句话总结）

• 递归：函数自己调用自己，是实现方式
• 搜索：遍历所有可能，是算法思想
• 回溯：递归搜索 + 撤销选择，是搜索的一种通用写法

六、最常考题型

• 全排列、组合、子集
• N 皇后
• 数独
• 电话号码字母组合
• 矩阵中的路径（单词搜索）
• 分割回文串