376_尚硅谷_Go核心编程_数据结构和算法-递归机制剖析.avi原创

好，那么我们来看一下这个递归，那递归呢，我们就是前面虽然讲过，但是呢，呃比较简单对吧，而且呢，没有涉及到回溯，那现在呢，我们来看一个，呃，相对来说比较复杂一点的，涉及到一个回溯的一个递归。呃，这个迷宫问题刚才我已经简单的说了一下，就是有一个小老鼠，它从这个位置开始出发。就是从这个位置。从哪呢，从这从这开始出发，然后呢，能够到达这个位置。到这个位置。嗯，当然他也有可能到不了，因为你不知道它是不是一个死路，打个比方，你从这儿。能够到达这个位置的前提是中间它的的确确有个通道。对吧，那假设你的迷宫是这样子的呢？这一个小圆圈，这一个小圆圈把它堵死了，它是不是就出不来了呀。诶，所以他也有可能是出不来的，还有一个最重要的问题是小老鼠从这个地方出发，就是从这地方出发它的路径。

他他从这出发到这儿，他的方式很多呀。他既可以从这儿过来，他也可以这样子哦。那当然还有很，还有很多很多选择。那你怎么知道他从哪儿走呢？哪一条路又是最短的呢？哎，这个就需要我们用这个递归的方式来解决，所以说迷宫问题呢，是一个非常经典的用递归解决的回溯问题啊，用递归可以解决这个问题啊，这是它的一个应用场景。啊，应用场景，那么我们就来看一下递归的这个基本概念，就是应就说一个应用场景呢，引出我们递归了。那地亏到底是什么呢？我们在前面其实已经讲过了，说说有点基础，那么有点基础呢，这样讲起来呢，会比较轻松一点。

简单的讲，递归它就是函数或者是一个方法自己调用自己，那么每次调用的时候，传入的这个参数就传输这个变量呢？它是不一样的。递归有助于编程，编程者解决复杂的问题，同时可以让代码变得比较简洁，就是它可以解决一些比较复杂的问题。啊，它可以解决一些比较复杂的问题，而且代码呢变得会比较简洁，所以说递归呢，它是在我们开发中用的还是比较多的，这这一点，比如说我们在上一次课，我们讲这个快速。排序的时候咱们就用到了递归，对吧，你明显感觉到它的速度会提升很多啊，这是递归的一个概念，那么递归的一个入门，递归呢，我们在前面是讲过的，当时大家可以简单的回忆一下，我们是怎么引出递归的呢？我们讲了两个问题，一个呢，就是讲了一个打印问题，第二个呢，我们讲了一个阶层的问题，我们都是用递归来来做的，好，那么现在呢，我们来回忆一下，就是借助这个递归的快速入门呢，把把这个递归的它的一个一个机制做一个非常简短的回顾，我们来回忆一下啊，就以哪个为例呢？就以就以这个为例，就以打印。

打印这个数字为例，我们看一下这个代码。来，朋友们。嗯，当时呢，我们是出了这么一个题，说有一个函数对叫test。Test test呢，它可以接受一个N值对不对，然后呢，如果这个N大于二，然后呢，N减减，再调用自己，这里就是地柜调用，哎，这里就是个地柜调用。这就递归了，那么调用完了过后呢，诶，它在进去过后呢，这个N还要继续减减，最后输出这个结果。

当时我们分析了一下它的结果是什么，大家应该还有点印象，我们来做一个简短回顾啊，我们再把这个东西呢，再敲一敲，再看一看这个结果是什么，再回忆一下他机制，然后呢，我们再说去解决刚才那个迷宫问题，大家可能会容易上手一点，因为这个东西呢，呃，有有一段时间没有用了，好，我们来把这个简单回顾一下啊，打开我们的Vs code，然后呢，我们来做这么一个回顾。好，来，走一个。文件夹，那么我们姑且把它叫做迷宫问题吧，迷宫。好，然后呢，我在这里写一个非常简单的一个一个回顾啊好，我们建一个文件夹，对。Recovervice。好，我们就叫一个测试吧，DEMO。DEMO。DEMO。

零一，好，我们来回顾一下原先的这个代码是怎么运行的啊，来简单回顾一下，打开这里package。Z。啊，打一个主包import。然后呢，这里面一个format。啊，然后呢，这里有个主函数。我们这写了一个T的函数，它可以接收一个N，对，它可以接收一个N。当然如果这个N。它是大于二的，就是它是大于二的情况下呢，我们就N减减，N减减完了过后呢，我们再去调用这个值。OK，我们是这样做的。啊，我们这样做的，然后这边呢，会有一个输出。啊，这边会有个输出，我这里输出的是N等于一个N啊是这样输出的，然后调用的时候，我们怎么调用的呢？回忆一下啊，我先定义一个N等于四。

然后呢，在这里我们去调用这个test，把这个N传进去。啊，传进去我们，呃，这个时候呢，就可以去调用它输出一个结果。对，这个结果是什么样子呢？我们简单的回顾一下啊，来我们看一下这个递归它调用的一个过程。就是借助这个案例回忆一下递归的一个调用过程，同学们，好的，那么我把这一段代码放在我们的这个表中，Excel表里面来一起回忆一下啊，同学们，这里面其实就是。站在里面，在站在里面起作用了，那当时是怎么来说的呢？说这是我们的一个内存。你可以把它理解成就是一个站。啊，这是一个内存。啊，内存，当我们的程序从这里开始执行的时候。好，这个呢，开始执行的肯定是，呃，刚开始执行的是这个主函数，你可以理解成在内存里面呢，就有一个站。

你可以这样去理解啊，说内存里面有一块占这个占呢，空间很大啊，占的空间很大。那他刚刚进来的时候呢，有一个占空间。叫主战。诶，大家可以这么去理解。那么这个主站里面呢，有一个变量N。等于是。对，N等于四。那么这个N等于是呃是在这负的值，然后呢，调用T的呃，N，那这个时候呢，它会去干什么呢？它会去开辟一个新的空间。这个新的空间呢，我们可以理解成又是一个新的站，但是它仍然是在这个大的这个站的一个这个这个空间里边啊，但是呢，它会在调用这个test的时候呢，先对这个现场做一个保存。

它会对它做一个保存，让这里面的数据呢，不要跟text的里面数据混在一起，所以说你可以认为它又开开了一个新的空间，但这个空间呢，仍然在我们这个站的范畴里边，因为战士大家都知道是先入啊，先入后出的，所以说他在开的时候呢，会把这个调用的函数，这个函数的新的站呢，压在这个站的上边。那么这样子代码呢，就进到了这里。那么这个时候呢，N因为是直传递，因为是直传递，所以说在这个站里边呢，又有一个新的N，但是呢，注意两个N不打架啊，然后呢，它传进来了，默认也是一个四，因为你是这个是四传进来的嘛，它也是好，于是他就判断if大不大于二，显然。目前这个是是呢，是大于二的，于是它就执行到这个N减减，注意N减减呢，是对哪一个N减减呢？是对这个地方的N减减，注意啊，待会儿一定要理解，不然的话迷宫问题你理解起来有点吃力啊，这个看起来很简单，但是一旦应用起来你就觉得很麻烦。

所以说这个N减减，减的是谁呢？减的是它，它就把这个四呢剪成了三，减成三过后呢，各位同学他又去调用test，于是乎这个地方呢，你可以认为它又开辟一个新站，也就是说。呃，也就是说原先的一个是在这儿，它调用到了这个位置。哎，他就他在这去，呃，调用了一个啊，起了一个test在这个地方呢，又启用了一个，又开开了一个新的。新的一个函数站。哎，那么这个地方又来了。为什么呢？因为它执行到test的N了，好根据我们函数调用的规则呢，它又开辟一个新的，那开辟一个新的过后呢，里面又有一个N，好，此时此刻各位同学，这个N。

这个N它就应该等于几呢？显然它就应该等于三，没问题，等于三，那么因为你是新的了嘛，它又进到这里面又来判断，但是要注意啊，他现在代码卡在哪的，就是这个站里面代码还停留在test的啊。还停在T的，大家一定要有个印象好，然后这个时候呢，判断N大不大于N大不大于二呢，显然在这个站里边，这个N是等于三的，它大于二，于是它又进到这个N减减，那N减减呢？减的是哪一个里面的呢？减的是这个占底的这个N，于是乎呢，他又把这个N变成了二，变成二过后呢，他又去调用这个test。好，这个时候太子呢，调用的话，又根据呃函数调用的规则，它又开辟一个新的函数站啊，注意这些基本原理一定要很清清楚啊啊好，然后呢，又开辟一个新单，那么我们就复制一份上到上面去了啊。

好的，又上到这边来了，没问题，那么这个地方这个N传过来呢，哎，这个N传过来的确。它就是二，它就是二，但是是一个新的啊暂停的，然后传进的十个二过后呢，它又到这来判断N大不大于二，显然这个时候呢，N等于二是不大于二的，于是他就执行这个站里面的这段代码。好，此时此刻他就会先输出一个N。它就会输出一个什么呢？N等于N等于二，这个就输出来了，输出来完了过后呢，这个站就执行完毕了，这个站执行完毕，根据以前的规则，我们的站顶呢就会往下走，但是呢，你可以你可以认为这个空间你你不去管它，反正站顶你你你认为啊，你可以这样认为。你认为这个地方有一个有一个有一个站点不停在变化啊，它又回回退到回退到这个位置了，好回到这个位置呢，它又开始执行这里面的代码，那么你你当时是从哪儿进去的呢。

是从这个T的进去的，好，T的进去过后呢，它就往下执行，执行到这儿，直行到这，它又输出这个站所，因为你现在这个是站点嘛，它就输出这里面的这个这个N，显然这个N呢，仍然是二，它又输出N等于二。好，这个N这个输出完了后呢，这个站又相当于执行完毕，这个站顶呢又往下面走，可以这样理解对不对，然后呢，你当时想想这个站是怎么过去的，他是不是也是从这个test的N过去的呀，所以说他这执行完了过后呢，他又执行这句话，那么这个时候呢，他又把这个N等于三输出来了。但当他把N等于三输出来过后呢，OK，他这个站又又执行完毕，他又回退到这个主站，主站里面呢，没有做任何事情都到这儿就退出去了，所以说结果呢，应该是N等于二，N等于二，N等于三，它是这么一个逻辑，好，这个就是它一个占的，就说呃，就说这个递归调用的一个流程，我们看看结果是不是跟我们想的一样啊同学们。

好，我们来保存一下，看效果，同学们。好，我们看看跟我们想的到底一样还是不一样呢？来执行小打开我们这段代码啊各位朋友。好，进到刚才我们写的这个代码，对是迷宫啊，迷宫DEMO01，然后呢，我执行它CD各位。我go一下go，让面点go跑起来，我们看效果。那么这个结果呢，跟我们想的是一样的，223没问题，好，那么明白这个道理过后呢，我在做稍微的一点点改变，各位同学我在做稍微的一点点改变，我把这个地方。加一个else OK，朋友们，我加一个else，那么加这个else过后呢，这个结果又是什么样子的呢？好朋友们，我们来分析一下，那你唯一的变化就是加了一个else，那么加了一个else的话呢，同学们可以想象到啊，你应该怎么去思考，那我们还是再来分析，因为这个里面的东西已经有了，所以说我们可以马上走主站还是这。

然后呢，掉第一次的时候。第一次啊，你你就从这开始走嘛。对，从这开始走，你当时这个N是没有进到这个衣服里面的，没问题，就说你在这个站顶的时候啊，同学们到这个站点的时候，你这个N是因为N不不大于二嘛，N不大于二，所以说它就执行这个里面的else语句啊，我把这个也切过来啊同学们。我把这个切过来，就是为为什么要把这个讲清楚呢？因为大家要非常的明白一点，就是说每一个站它的代码它是独立，独立的去执行一份啊，并没有那个混在一起。

好，我把这个呢再拷贝过来。好，针对站点的时候，我们的指针就是说我们代码执行到哪了呢？执行到这儿了。啊，执执行到这个else里面了，因为你这个N是不不大于二的，所以它进到这里面去。啊，进到这里面去，他肯定是要输出这个N等于二的，它会输出。它会输出好，他一旦输出过后呢，他又回退到这个站，那么我们站点往下挪动。好，往下挪动的话呢，呃，大家想一想，这个时候它这个对于这个站来说，它是到这儿进到这个test的。那么进到这里面去，因为你这个地方已经进入if了，所以说这个地方是不会输出的，这个不会输出，于是这个站也结束了，到这儿大家想这个地方又是怎么进去呢？它也是进去的，说这个呢也不会输出。最后其实只输出一个N等于二。所以大家要明白这个每两点啊，就是数据是独立的，而且呢，他们代码也是要根据这个实际情况去执行，因此呢，在加了else过后，输出的结果应该只有一个占顶输出了一个二。

哦对，是这样子的，来我们再执行一下。报一下。我们看效果。OK，我发现的确如此。好，明白这个基本道理过后呢，我们就可以往下继续讲解了，来把刚才讲解的这个东西做一个简单的板书。啊，做一个简单板书，好，我稍微的整理一下刚才讲解的内容啊，同学们。那么刚才我们回顾了一下递归调用的机制，怎么说的呢？来看一下。哎，首先我提出，呃，一个递归的一个应用场景。对，递归的。递归，好，我把它反述一下，这是我们的标题二对，我做先做了一下一个应用的场景递归。

递归的一个应用场景啊，应用场景什么呢？就是这个迷宫。迷宫的一个问题，对吧，诶，我提出这么一个观点。那么引起大家的思考。啊，当时是怎么说的呢？诶，我是这么说的，迷宫对这样子的。好的，然后由这个迷宫问题呢，我们就呃引出了这个递归的一个概念，就是什么是递归呢？简单的讲，递归就是自己调用自己，对吧，那为什么要自己调用自己呢？因为很多概念就是有很在我们现实的这个问题里面有一种逻辑，就是很多是自己去调用自己，比如说比如说那个咱们要去显示一个目录数。他是自己调用自己。对，你再比如说啊，我们这个排序，排序也也有可能要自己调用自己，这还有查找二分查找都有这种概念，很多这个概念都是他要用到自己调用自己，这这种逻辑很多，因此呢，就引出这个递归好，然后呢，我又借助我们原先讲的一个小案例，帮助大家进行了一个简单的回顾，诶，我们回顾了一下递归的一个规则。

好，来看一下。递归的一个。啊，规则我们回顾了一下，对啊，当时呢，是一个打印问题，还有一个阶层问题，对。好，然后呢，我把这个分析的这个图给大家看一下啊，就是快速入门的一个图。二。快速入门的一个示意图。哦，好，我们把这个呢，也给大家放在笔记里面去。那当时是怎么说的呢？就这么讲了一下，对。大家看一下这个逻辑啊。好，把它放在我们的笔记里边去。好，非常的简单，非常简单，好这个是一个回顾，就相当于说把递归的一个机制，还有它的一个应用的场景呢，做了一个回顾，好关于这块我们先说到这。