一、什么是递归函数自己调用递归1.为什么会用递归首先我们先看归并排序快速排序和二叉树的遍历都出现了相同的子问题二、快速排序Quick Sort1. 核心思想选基准 分区 递归在数组中选一个元素作为基准值pivot一趟遍历把数组划分成两部分左边所有元素 ≤ 基准右边所有元素 ≥ 基准递归对左子数组、右子数组重复分区操作直到子数组长度为 1天然有序2. 简易流程示例数组[5,3,8,4,2]选基准比如选第一个元素5分区后[3,4,2, 5, 8]递归排左[3,4,2]、递归排右[8]逐层递归完成全局有序3. 关键特点不稳定排序相等元素相对顺序会被打乱原地排序只需要常数级额外空间最好 / 平均O(nlogn)最坏数组完全有序 / 逆序O(n2)实际工程中最快常数开销小系统内置排序大多优化版快排4. 缺点极端数据下性能退化需要优化三数取中、随机选基准三、归并排序Merge Sort1. 核心思想二分拆分 递归排序 有序合并不断将数组从中间二分拆分直到每个子数组只有 1 个元素单个元素天然有序逐层向上合并两个有序子数组合成一个新的有序数组最终合并为完整有序数组2. 简易流程示例数组[5,3,8,4,2]拆分[5,3,8]、[4,2]→ 继续拆到单个元素最小单元[5] [3] [8] [4] [2]两两合并[3,5]、[8]、[2,4]继续合并[3,5,8][2,4]→ 最终[2,3,4,5,8]3. 关键特点稳定排序相等元素相对顺序保持不变非原地排序合并时需要额外辅助数组空间复杂度 O(n)时间复杂度稳定最好 / 平均 / 最坏 都是 O(nlogn)适合外部排序硬盘大文件排序、要求稳定排序的场景4. 缺点需要额外内存空间开销大小规模数据下不如快排快本质主问题-相同子问题子问题-相同子问题如何理解递归1.递归展开细节图2.二叉树题目3.宏观看待递归问题如何写好一个递归1.找到一个相同的子问题----函数头的设计2.只关心某一个子问题如何解决--函数体的书写3.关注一下递归的出口即可如何到一个问题不能再分割了一、核心概念区分1. 遍历 vs 搜索遍历是一种形式 / 过程指按某种顺序访问数据结构树 / 图中的所有节点。搜索是目的 / 行为指在遍历的过程中寻找满足特定条件的目标节点或状态。一句话总结遍历是形式目的是搜索。深度优先遍历DFS、深度优先搜索DFS本质是同一个过程只是侧重点不同常直接叫 DFS。宽度优先遍历BFS、宽度优先搜索BFS同理本质相同常直接叫 BFS。2. DFS深度优先搜索 / 遍历核心思想一条路走到黑走不通再回溯递归 / 栈实现。过程从起点出发先往最深的分支探索直到尽头再回退到上一层探索其他分支。图中的示意箭头是 “深入” 和 “回溯” 的过程一条分支走完再走另一条。特点适合解决路径类问题、全排列、组合问题能快速找到一条解但不一定是最优解。3. BFS宽度优先搜索 / 遍历核心思想按层遍历一层一层向外扩散队列实现。过程从起点出发先访问所有直接相邻的节点再访问下一层节点就像水波纹一样扩散。图中的示意红色横线代表 “层”按层依次访问节点。特点天然适合求最短路径 / 最少步数第一次访问到目标节点时路径就是最短的。二、关系梳理暴搜暴力搜索是一个统称指通过穷举所有可能的状态 / 路径找到目标解。暴搜的两种典型实现方式深度优先搜索DFS用递归 / 栈实现穷举所有路径。宽度优先搜索BFS用队列实现按层穷举所有状态。包含关系暴搜暴力搜索枚举出全部的情况 ├─ DFS深度优先搜索/遍历 └─ BFS宽度优先搜索/遍历三、核心对比方便你快速区分对比项DFS深度优先BFS宽度优先实现方式递归 / 栈队列遍历顺序一条路走到黑回溯再走其他路按层扩散一层一层访问适用场景路径问题、全排列、组合、连通性最短路径 / 最少步数、状态层序扩散空间复杂度树 / 图深度递归栈深度最宽层的节点数队列大小是否一定找最优解不一定需额外剪枝是第一次找到的就是最短路径四、补充说明树和图都可以用 DFS/BFS区别在于图需要额外处理访问标记防止循环访问比如环而树天然无环不需要。暴搜DFS/BFS的核心是穷举时间复杂度高数据量大时会超时实际中常配合剪枝优化。决策树回溯和剪枝1.、回溯 vs 剪枝关系与区别表格概念核心作用本质必须吗回溯遍历所有可能的路径实现穷举DFS 的 “撤销选择” 机制✅ 必须没有回溯就没法遍历所有分支剪枝提前终止无效路径减少递归次数暴力搜索的优化技巧❌ 非必须但大数据量下没有剪枝会超时一句话总结回溯是基础框架让你能把所有可能都试一遍剪枝是性能优化帮你把没用的路径提前砍掉跑得更快。2、常见的剪枝类型面试高频可行性剪枝当前路径已经不符合题目条件直接停止。例迷宫问题里走到墙外面了就不继续走了。最优性剪枝当前路径就算走完也不可能比已经找到的最优解更好直接停止。例求最短路径时当前步数已经超过已知的最短步数就不用继续搜了。重复性剪枝避免生成重复的状态 / 排列。例有重复元素的全排列、组合问题里跳过相同的分支。二、典型例题1.汉诺塔问题1.如何解决汉诺塔问题N1,也就是有一个盘子直接把A中的盘子放到c中N2时想办法把最后一个盘子放到c中借助b以此类推二、为什么可以用递归解决大问题的时候---相同子问题子问题--相同类型子问题因为这个题总是在重复一个动作把A最后的数借助B放到C上边1.把a上边两块借助C放到B上2.把a中最后一个数放到C上3.把B上的盘子借助A放到C上也就是说不管你N(未知数的个数)等于几最后都是完成这三个动作三、如何编写递归代码1.重复子问题-函数头将柱子上的一堆盘子借助y柱子转移到Z柱子上边 void dfs(x,y,z,int n)函数体1.dfs(x,z,y,n-1x中n-1个数据借助z放到y上2.x.back()-z3.dfs(y,x,z,n-1)递归的出口就是N1直接把x上的块直接放到Z上只有一个数的情况大家有没有一个疑问就是为啥不能直接把X上边n-1个数直接放到y上为啥还要借助Z其实如果直接放y上就直接违背了我们调用递归的初衷递归函数必须满足全部的情况如果直接放到Y上不借助Z少了一个参数那这个意思就是把x上的n-1个数也可以直接放到z上了大盘子就叠在小盘子上不满足题意如果想把x上的数据移动到z上必须借助y如果你光看x上的数据移动到y上不用借助z的话那最开始x的最后一个数据移动到z怎么解决少了一个参数就没办法解决那个问题了四、代码编写class Solution { public: void hanota(vectorint A, vectorint B, vectorint C) { dfs(A,B,C,A.size()); } void dfs(vectorint a, vectorint b, vectorintc,int n){ if(n1){ c.push_back(a.back()); a.pop_back(); return; } dfs(a,c,b,n-1);//把a上n-1个数据借助c放到b上 // for(int i0;ib.size();i){ // std::coutb[i] std::endl; // } c.push_back(a.back()); a.pop_back(); dfs(b,a,c,n-1);//把b上的数据借助a放到c上 } };