网站设计策划书案例,漳浦建设局网站,出色的网站,聚财洋气三个字公司名字本专栏内容为#xff1a;递归#xff0c;搜索与回溯算法专栏。 通过本专栏的深入学习#xff0c;你可以了解并掌握算法。 #x1f493;博主csdn个人主页#xff1a;小小unicorn ⏩专栏分类#xff1a;递归搜索回溯专栏 #x1f69a;代码仓库#xff1a;小小unicorn的代… 本专栏内容为递归搜索与回溯算法专栏。 通过本专栏的深入学习你可以了解并掌握算法。 博主csdn个人主页小小unicorn ⏩专栏分类递归搜索回溯专栏 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 前言 递归什么是递归为什么会用到递归如何理解递归怎样写好递归 搜索深度优先/宽度优先关系图拓展搜索 回溯与剪枝 递归
什么是递归
在讲解递归前我们首先要知道什么是递归 递归我们之前是接触过的 在c语言中我们详细学过递归数据结构中的快排二叉树也用到了递归。
简单来说递归就是函数自己调用自己。
为什么会用到递归
那么为什么会用到递归呢 举两个例子 例子一 在这个二叉树中我们用前序遍历来遍历这个树 先访问蓝色节点然后将这个树分为左子树和右子树 在左子树中我们继续根据前序遍历根左右进行划分 依次内推将这个树不停的划分成根左子树右子树。
我们的主问题是根左右而子问题也是根左右子问题的子问题的也是根左右。子问题是相同的。
例子二 我们复习一下快排 找一个key将数组从key位置划分为左右两个部分让这两个左右部分排序。而让左右两个部分排序又可以进行划分在左右两个数组继续用Key进行划分 依次内推不停的划分知道最后不停划分为两个元素后大小就很好比较。
这个例子我们也可以发现主问题是通过key将数组划分为两部分而子问题也是通过key将数组划分为两部分子问题的子问题也是通过key将数组划分为两部分。
通过这两个例子我们想告诉递归的本质 递归的本质其实就是重复的子问题也就是说主问题可以划分成一个跟主问题相同的子问题。
如何理解递归
那么如何理解递归 这里给出两点
递归展开宏观看待递归的过程
想要理解递归就要画一下递归的展开图将递归通过展开图展开会很明显看到递归相关细节返回条件如何递归
其次我们要宏观看待一个递归得到过程 具体分一下几步
不要在意递归的细节展开图把递归的函数当成一个黑盒相信这个黑盒一定能把这件事做好
就比如我们的二叉树后序遍历 首先我们要通过根节点来进行遍历黑盒装什么呢 我们知道后序是左-右-根 那么我们就坚信dfsroot-left一定能帮我们实现进行左子树的遍历dfsroot-right一定能帮我们实现进行右子树的遍历 这就相当于是我们的黑盒。
但是还要注意一个细节 为了防止进行死循环我们要写一个出口也就是返回条件
怎样写好递归
有了上面的经验怎样写好递归就很简单
先找到相同子问题这就是我们函数头的设计只关心某一个问题是如何来的这就涉及到函数体的书写注意细节递归函数出口防止死循环
搜索
深度优先/宽度优先
首先要知道什么是深度优先什么是宽度优先 深度优先深度优先就是一条道走到黑我们也叫DFS通常用递归实现。 跟二叉树遍历一样从根开始一直往下走知道左子树最后一个节点走完不能再走了就往上走。
宽度优先宽度就是一层一层的剥开我们也叫BFS通常借助队列实现。 就比如还是二叉树遍历我们一层一层的进行遍历将每一层遍历出来。 那么深度优先遍历和深度优先搜索又有什么区别呢 其实遍历和搜索大致是一样的记住一点遍历知识形式就比如二叉树遍历只是根据规则进行遍历而搜索是遍历里面的值因此也叫搜索。
关系图
其实搜索也叫暴搜暴搜顾名思义就是暴力枚举一遍所有的情况。
拓展搜索
其实我们之前学过的全排列就是一个搜索问题。
以123三个数的全排列为例我们高中就学过要想枚举出全部的结果用树状能很清晰的表达出来 通过树状这样画出来就不会漏解的情况。
这棵树我们也把它叫做决策树。
回溯与剪枝
什么是回溯什么是剪枝其实他们两的本质也还是搜索 回溯还是以二叉树遍历为例 当遍历到左子树的最左节点他的左子树为空那么就要返回而这个返回的过程就是回溯。
以这个迷宫为例子 第一段红线走到尽头发现走不掉了往回走的过程就是回溯。
根据暴搜原理会一直往右走走到尽头向上走走到尽头发现到头了就往回走然后往左走往右走依次内推。在这个过程中有一段是没有必要走的路段没有价值的路段在本图中是画叉的路段这个画叉的路段我们就可以舍去舍去的过程就是剪枝。
