一、递归Recursion1. 概念函数自己调用自己把大问题拆成更小的同类型问题。2. 两个必备条件递归出口base case不再递归直接返回结果递归式把问题规模缩小3. 经典示例求阶乘1234intfact(intn) {if(n 0)return1;// 出口returnn * fact(n - 1);// 递归式}4. 本质系统使用栈保存每一层调用太深会栈溢出stack overflow二、搜索Search搜索就是在所有可能情况里找答案。常见两类深度优先搜索 DFS一条路走到底广度优先搜索 BFS一层层扩散递归最常配合DFS。三、回溯Backtracking1. 概念递归搜索 撤销选择 回溯选一条路走走不通就回退一步尝试其他可能典型场景排列、组合、子集、N 皇后、数独2. 回溯通用模板必背1234567891011voidbacktrack(路径, 选择列表) {if(满足结束条件) {记录答案;return;}for(选择 : 选择列表) {做选择;backtrack(路径, 选择列表);撤销选择;// 回溯核心}}四、三个经典例子一看就懂例 1全排列回溯经典求[1,2,3]的所有排列1234567891011121314151617vectorvectorint res;vectorint path;boolvis[10];voiddfs(vectorint nums) {if(path.size() nums.size()) {res.push_back(path);return;}for(inti 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子集搜索所有可能12345678voiddfs(vectorint nums,intu) {res.push_back(path);for(inti u; i nums.size(); i) {path.push_back(nums[i]);dfs(nums, i 1);path.pop_back();}}例 3斐波那契纯递归1234intfib(intn) {if(n 1)returnn;returnfib(n-1) fib(n-2);}五、三者关系一句话总结递归函数自己调用自己是实现方式搜索遍历所有可能是算法思想回溯递归搜索 撤销选择是搜索的一种通用写法六、最常考题型全排列、组合、子集N 皇后数独电话号码字母组合矩阵中的路径单词搜索分割回文串到此这篇关于C 递归、搜索与回溯的文章就介绍到这了,