377_尚硅谷_Go核心编程_数据结构和算法-递归相关说明.avi原创

好朋友们，我们来看一下下面这个迷宫问题怎么去解决呢？首先啊，首先我们看一下这个迷宫。呃。呃，这个我们这样子说啊，先先说的这个递归除了能够解决迷宫问题呢，还有哪些问题也会用递归来解决，你比如说。八皇后问题。啊，有有同学可能听过八皇后对吧，很经典的一个八皇后问题，然后还有像这个汉诺塔。汉诺塔呢，它也会用到递归，如果说我讲完这个迷宫回溯过后呢，同学们能够用一个算法解决这个汉诺塔，那你就真的听懂了。但有些同学老师汉洛塔我自己都不知道怎么弄，我五个都玩不过去，那你写不出来代码的，说老师，比如说汉洛塔你自己，我给你个三个三三个盘子，你都把它整不过去，那你想把这个代码写出来是写不出来的啊，我以前一直讲过，就是说我们写代码的前提是你作为一个程序员，你自己知道怎么做，你才可能把代码写出来，如果你自己都玩不了这个游戏，你想写上写不出来的，所以说自己想一想看到他，他是怎么玩的啊，然后呢，这个呢也到时间也做一个，呃作业题，想引起大家思考，就是我希望同学们听完我这个迷宫回溯过后呢，自己可以把汉洛塔的这个解法能写出来，当然网上东西也很多，对吧，你自己一一搜也能搜到好多，但是你要看得懂。

好，然后呢，阶层问题，迷宫问题，求和篮子的问题，比如说我在昨天布置了一个，呃，2005年的一个谷歌编程大赛里面，求和篮子怎么放，对对，把这个篮，把这个球放在各个篮子里面，有多少个情况，哪种情况是我需要的，就可以用B，就又可以用递归来解决。啊，然后呢，还有这个占，就是占的一些问题呢，也可以用递归来简简化啊，递归来简化这个是它的一个应用场景啊，然后呢，我们这样子啊，我们这样子来说递归呢，它要遵循的一些原则，我们再来讲讲。递归呢，它用的时候它是有有一定风险的，你打个比方，比如说老师为什么在这方要减减，而不是加加，如果我把这方写成加加，那么同学们可以考虑这个地方就会成为一个死归啊，它就是不是递归了，它变成这个东西了。

它变成一只死龟了啊，他变不是死鬼啊，是死龟。死归这就死在里面了，为什么？因为我们这个递归有一个前提，就是说他一定要向退出递归的条件逼近，你看为什么是减减，而不是加加，所以说递归里里面呢，有些规则大家看一下啊，我以前也说过，有四个规则是需要大家在使用递归的时候特别注意的。第一个递归，在去调用一个函数或者方法时，它会创建一个新的受保护的独立空间，这一点大家要从机制上易于理解。什么叫受保护的独立空间呢？就是刚才老师画的这个图，这个呃，我们编译器在底层，在底层它再去开创一个新的占空间的时候，它会保存这个现场。

那么他会怎么保存呢？他会留一个地址，他会说，诶，我到哪去了？于是乎，他会把这个地址压入到这个新的站，等到他执行完了过后，他会从这个地址再重新退回来。OK，所以这点呢，大家要要清楚，就是说它会有一个保护的机制，这个呢是它编译器底层做的，这是第一点，同学们要清楚，第二点呢，函数的就递归调用的时候，函数的局部变量是独立的，不会互相影响，即使你的变量名相同也不会，但是有一点同学们，但是有一点啊，有些时候你恰恰要要用到一个什么特点呢？就是你所有的这个函数用的却是同一个变量，也有可能用到，比如说我记得我们有一个应用场景，就是比如说这个这个这个站，这个站我们将来也有可能有这种需求，就是我们希望你在每一个站里面用到的，用到数据是同一个，比如说我们前面讲的这个叫做快速排序，如果是快速排序，你们发现我们在每一个站里面用的是同一份这个数组的时候，那么这个时候传递的时候呢，就应该传递引用的方式，比如说也也有这种可能，比如。

这是一个数组。这是一个数组，我们在进行快速排序的时候，大家应该感觉到他们每一个站用的这个用的数据，这个指向的一个数组呢，是同一个数组，不会是不会是两份，这也是有可能的，比如说这次我们解决迷宫问题，就必须传同一份传传同一份这个地图过去，否则的话呢，这个就会出问题啊，那肯定要出大问题的，所以大家一定要要分清楚你的这个实际情况，如果你在这个递归里面。每每一个站里面，你要引用同一份数据空间，那就得引用，如果你是独立的，比如像这个N啊，你认为是每一个地方是不同的变量，那你就用什么呢？直传递，这点大家要很清楚知道啊，所这这是个基本常识问题。第三点，同学们递归必须向退出递归的条件逼近，否则就是无限循环，你说刚才老师写的这个东西，如果没有减减你变成你要么不动，假设你不动啊，假设你这样子他也是个死规，因为它进去就推不出来了，你看简单的看一下这个这个应用场景，你看我一写死在里面了。

啊，出不来了，已经没没没戏了，你看他他他已经死在这里面了，只要你看到这个类似于这样一个提示说啊什么什么就不停打，一句话就在这个第九行不停的打，像这种情况一般来讲都是出现一个死循环了。啊啊，这个死循环肯定就是一般如果是递归的话呢，肯定就是你出不来了啊，所以说这个大家要一定要找到这个条件啊，一定要分析出，分析出这个退出，退出这个地柜的一个条件，还有一点。

当一个函数执行完毕后，或者它遇到后就会返回。他要遵守一个原则，遵守谁呢？谁调用就将结果返回给谁啊，同时函数执行完毕或者返回时，该函数本身呢，也被系统销毁了，就是这个空间呢，相当于被回收了啊，相当于被回收了，好，这些原则大家要注意一下。好，我把这个呢，给大家简单的板述一下，刚才老师讲的这这点东西啊，一个是递归解决什么问题。只要是涉及到一个逻辑重复，重复的一个地方呢，都可以用到递归。OK。好，我们把它写到这里啊，比如说像这个经典的就是各种数学问题，对吧，各种数学问题。好，第二个呢，就是将占解决的问题呢，可以用递归来进行简化。

对，然后呢，我们这儿又说了一下递归的四个重要的原则，大家要有一个认识啊。好，我把它板书一下，这是我们说的第三点。啊哪哪哪四点呢，第一个执行的时候啊，它会创建一个受保护的呃独立的空间，这一点大家要很清楚，第二个呢，局部变量是独立的啊，互相不影响，但是我要补一下啊，如果希望呃每一个函数站用到相同的数据，那要用引用啊传递啊，如果希望。如果希望不同的站，就是各个站吧，各个函数站。函数站。使用使用同一个同一同一个数据啊，但是数组也可能是一个全局变量啊，不知道啊，这个使用到同一个一般使用使用什么呢？使用这个引用。

引用。啊，引用。引引用传递。引用传递，大家如果是全局变量也可以啊，如果是个全局变量它也可以好第第三点递归呢，需要你分析出来，你要分析出来这个递归退出的一个条件，就是想退出递归的条件逼近，那么这个条件是什么呢？你自己要分析，你比如说我们待会儿讲的迷宫问题，如果你分析不出来什么时候退出这个地归，你肯定是出不来的，这个小老鼠就在这个迷宫里面转转转，最后就晕了。就你一定要分析出来什么时候。这个这个递归就算是结束了。就是你小老鼠什么时候算是结束呢，他什么算是找到这个，什么算是他找到了这个点，什么时候又算是找不到，就说因为这个迷宫呢，待会儿解决的问题，他有两种可能，第一种就是的的确确他就找到这个出路了。还有一种可能性就是。他就他就是找不到。

他死活找不到，那他如果找不到，你也不能让他一直在里面找啊。你要把这个条件分析出来。对，你得分析出来，什么时候是找得到，什么时候确实找不到，你都要分析出个条件，不然的话，我们这个这个就就就一定是失败的，好，这是一个重要的地方啊，就是说退出递归的条件分析，这个是谁来做呢？是程序员自己要分析。程序员自己自己必须分析出来。那如果你分析不出来，那对不起，你这个肯定是做不了的啊，这做不了好后面呢，这个地方就是什么时候返回啊好，这是它的一个原则，那原则讲完了过后呢，同学们，现在我们就来开始写东西了啊，我们开始写东西，那么我们来看一下迷宫问题怎么解决。好，首先呢，我们来看迷宫的这个他的一个需求，刚才已经讲过了，我做一几点说明，我们看一个Java啊，看一个Java的代码。我们来看一下它是怎么跑起来的。打开。

打开我们这边的一段代码吧，大家看这呢有一个迷宫，迷宫案例，我把它跑一下，大家先看一下。我我找一个比较简单的迷宫啊，我不找那个很复杂的迷宫，我找一个简单的迷宫。好像这个是我写的吧，我看看这是以前写的，我看一下。这个代码应该是比较哦，这个是比较复杂的一个。哦，这个这个是简单的，对，就它就它这个是比较简单的，这个简单的容易把这个东西说清楚，因为我设计的是八行七列的一个泥宫啊，它就比较简单加吧。哦，然后呢，迷宫。米。弓跑起来看一下。哦，看一下。好的好，同学们看，这个呢，是一个比较简单的迷宫，我就设计了，呃，两个挡板。红色的呢，就代表这个，呃，代表是一堵墙。

大家你想一想啊，呃，你红色是代表一堵墙，那么你在程序里面怎么去表示一堵墙呢？好，然后小球就从这儿开始走，我就开始走了啊走。好，你看这个小球，我每隔一秒让他走一下，因为我控制了一下这个这个显示啊，好到这来结束了。好，大家看到他是这样走的，它这样走的，那么他为什么这样走而没有，为什么他是这样走的呢？它是这样走走过来的呢？而不是这样走过来的，好，这个就涉及到你的这个策略了，你你是怎么决定，你你的策略是什么样子，会直接决定将来这个小球走的这个路径，那待会儿呢，我会讲到这个啊，这这个知识点啊，好，这个大家先看清楚了，好那现在呢，明白这个要写的这个东西过后呢，我们接着来继叙玩啊继叙文那么有几点先说明一下，说明几点啊，第一点因为我们没有学习这个构语言的这个它的GIGTK这个呢，是他一个图形界面。

啊，因为这个用的也不多，所以说呢，我们整个这个代码就在后台完成就可以了，就说我我模拟一个数组。把这个数组的通路给他打出来，就是它的通道，它的通路是什么，大家看到这个通道就行了，第二点呢，小球得到这个路径呢，和程序员设置的找找路的策略有有关系，我待会儿这样设计一个套路啊，我们是先执行先上向上找。再向下找，再向左找，再向右找，就说我我我的策略是让这个小球先向上探，然后呢，如果上走不通，再让它向下探，如果下面也走不通，让它向左边探路，如果左边再走不通，再向右看，那么如果他走不通的时候，他就回溯，它就回溯好，那么呢，现在我留了一个思考题，待会我讲完了过后呢，我希望同学们做一做如何求出最短路径，就是你能不能不能把最短路径做出来，好，现在呢，我们开始做这个题了。

好，同学们，老师呢，先来开始完成这个案例，那么我在讲的时候呢，注意听啊，好，我把这个题先放在这里。我们要做的就是它。好的，这是我们要准备做的题啊，好，这取段。