网站建设网站设计做网站怎么赚钱广告
作者简介：大家好，我是未央；
博客首页：未央.303
系列专栏：递归、搜索与回溯算法
每日一句：人的一生，可以有所作为的时机只有一次，那就是现在！！！！！
文章目录
前言
一、递归算法
1.1 什么是递归？
1.2 为什么会用到递归？
1.3 如何理解递归？
1.4 如何写好一个递归？
二、搜索算法
2.1 深度优先遍历vs深度优先搜索
2.2 宽度优先遍历vs宽度优先搜索
2.3 扩展搜索问题
三、回溯算法
总结
前言
今天我们将进入到递归，搜索，回溯算法，这些算法在我们笔试中非常重要，必须要熟练掌握，本节内容主要带着认识一下这些算法，了解其本质，后面会有很多例题来巩固这些算法！！！！
一、递归算法
1.1 什么是递归？
我们要学会递归算法的使用，首先要了解它是什么，才能更好的掌握和使用它。
简而言之，递归：函数自己调用自己的情况；直到碰到终止条件，返回结果的过程。
递归可以看作两个过程，分别是递和归。
递就是原问题把要计算的结果传给子问题；
归则是子问题求出结果后，把结果层层返回原问题的过程。
1.2 为什么会用到递归？
递归的本质：
即主问题可以推出与主问题相同的子问题；
而子问题又可以继续推出与子问题相同的子子问题；
实例图示说明：
（1）二叉树的遍历：
（2）快速排序算法
（3）归并排序算法
1.3 如何理解递归？
第一步：递归展开细节图；
归并排序举例：
递归展开图（int arr[] = { 7,5,6,3,9,8,2,1,4,5 };）
第二步：二叉树的递归；
二叉树递归举例：
先简单的定义一个 二叉树；
像这样的二叉树：
（1）不要在意递归的细节展开图；
（2）把递归当成一个黑盒；
（3）相信这个黑盒一定能完成这个任务；
1.4 如何写好一个递归？
第一步：
先找一下是否有和主问题相同的子问题！！！！！-----> 关系到函数头的设计；
第二步：
只需要关心某一个子问题是如何解决即可！！！！-----> 关系到函数体的书写；
第三步：
最后再注意一下递归函数的出口即可；
代码示例说明：
（1）二叉树的递归：
代码实现：
//二叉树的后续遍历 void dfs(TreeNode* root){//递归的返回条件 if(root == null) return;//先递归遍历左子树 dfs(root.left); //再递归遍历右子树 dfs(root.right); //最后遍历根结点 printf(root.value);}
（2）归并排序：
代码实现：
void merge(nums,int left,int right){ //细节：出口； if(left >= right){int mid = (left+right)/2; merge(nums,left,mid); merge(nums,mid+1,right); //合并两个有序数组 }
二、搜索算法
2.1 深度优先遍历vs深度优先搜索
深度优先遍历（深度优先搜索）：一条路走到黑，走到不能继续走的时候就返回；
两者实际是一样的概念；而不同的是：
遍历是形式；搜索是目的；
图示说明：
2.2 宽度优先遍历vs宽度优先搜索
宽度优先遍历（深度优先搜索）：又叫
层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。两者实际是一样的概念；而不同的是：
遍历是形式；搜索是目的；
图示说明：
2.3 扩展搜索问题
搜索方式，不仅仅局限于二叉树，图类等；还可以对于一些全排列，如果列举问题能用决策树的图示表示出来，依然可以用搜索来解决问题；
三、回溯算法
回溯算法定义：
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。一个典型的应用是走迷宫问题，当我们走一个迷宫时，如果无路可走了，那么我们就可以退一步，再在其他的路上尝试一步，如果还是无路可走，那么就再退一步，尝试新的路，直到走到终点或者退回到原点。
回溯的本质：回溯的本质就是深搜；
图示说明：
总结
