00:00
同学们,我们继续来学习数据结构和算法,那么下面呢,我们来给大家讲一个数据结构和算法里面的递归,各位啊,我那首先呢,我们还是老规矩,有一些同学呢,呃,对递归还不太了解,有些同学呢,对递归已然有一些了解了,我们这样子,我们把递归的它的一个调用机制做一个简单的回顾,然后呢,再讲递归的应用。我们首先呢,来看一个递归的应用场景,同学们请看,在这个地方呢,我们可以看到这儿有一个界面,这个界面呢是一个迷宫。是一个迷宫,那么这个是小老鼠找家的这么一个小案例,说这里有个小球,小球呢是从这个位置,就是我现在画的三角的这个位置开始移动。那么它最终移动到哪个位置去呢?移动到箭头所在的这个位置就表示。
01:00
小球能够找到他出这一个迷宫的路径。就这么简单,也就是说这个就叫迷宫回溯问题,也叫迷宫问题。那在这个应用代码里边呢,我们就会用到一个叫递归的这么一个知识,那么递归呢,也叫reccu啊,这个是递归的英文。好,那么我们给大家演示一下这个小案例,给大家演示一下这个小案例,在我给大家分享的资料里边呢,有数据结构,经典的应用场景里边,大家可以看到这儿有一个迷宫案例,我们来运行一把。给大家看一下啊CMD。好,同学们可以看到在这里呢,我运行运行一把叫Java迷宫。OK,同学们看。那么待会儿呢,我点走。
02:00
啊,同学们先先给大家简单的解释一下啊,红就是这个方块,红色的方块表示什么意思呢?红色的方块,红色的方块。我把这个变成蓝色啊,红色的方块呢,代表墙。就是小球不能走的,大家看在这个迷宫里面呢,中间还有两堵墙。那小球呢,需要绕过这个墙,找到这个位置,也就是说小球从这里开始走,然后呢,最终呢,找到这个位置就代表小球能够。呃,从这个迷宫里面出来。这里面肯定用到了递归,那么我们来试一下,我点走,大家可以看到小球从这里开始出发。对,你看同学们,看他是不是自己找了一条路,然后呢,到这个位置。大家看到没有,小车从这自己找了一条路到这来的,那么同学们看在我们的后台,同学们有发现没有,在我们的后台里边呢?从这开始用二标识的。
03:07
用二标识出来的这个坐标就是它。在迷宫中移动的一个路径。迷宫中移动路径,那这里呢,就是迷宫问题的一个经典的一个小案例,好,那看完这个案例以后呢,同学们我们给大家简单的回顾一下,呃,这个递归它是一个什么东西,首先给同学们看一下递归的概念,OK,那么因为我们听视频的同学呢,有些没有学过这个。呃,这个递归回溯有些学过,我简单介绍一下啊,递归简单的来讲呢,就是什么呀,它就是有一个方法自己调用自己,比如说你有一个test的一这个方法,Test的一这个方法里边呢,它在函数方法内,它调用自己,这个就叫递归。啊,每次传入的不同的变量,就是每次它在调用的时候呢,传的变量不一样,递归它的作用是有助于编程者解决复杂的问题,你比如说刚才我们这个迷宫回溯,如果用递归来解决,其实用不了几几行代码就搞定了。
04:16
而且呢,它可以让我们代码变得比较简洁,OK,这是递归的一个基本概念,那现在呢,我们写两个小案例,帮同学们来回顾一下递归的调用机制,好的,那么现在我举两个小案例啊,两个案例。两个案例,第一个案例呢叫打印问题,第二个案例叫阶层问题,那么帮助同学们回顾一下地柜的机制,这里呢,主要是做一个简单回顾,如果你已经学过这个递归了呢,你相当于巩固一下好吧,那首先呢,我们看这里有一段代码。这个代码呢是呃,这样写的,有一个test的方法。里面呢,他接收了一个N这么一个行参,那么当N大于二的时候呢,它在这里面调用自己了,看到没有这个地方,这有个test。
05:07
这个test大家有助于观察到,就是这个test调用的其实就是他自己。他又回来掉自己了,其实就在这地方形成了地归。OK,然后呢,下面有一句输出语句,这叫打印问题。来,同学们,我们先来看一段代码,看看这个递归输出什么,打开我们的ecl。打开我们的eclipse,好OK,打开这个问题以后呢,同学们,我们往这个地方来看一下代码。看一下代码,OK,现在呢,我们新建一个包,我们新建一个包。好,这个包呢,因为是专门讲递归的是吧,我就取个名叫。OK。好,现在呢,我们就把这些先全部都关闭好吧,全全部关闭。
06:04
关闭网络过后呢,我们在这里写一段代码。简单的我们来测试他一下,比如说我们就叫reccucu test OK,那这是我们的一个,呃,递归机制的回顾。好,首先呢,这段代码我就不写了,因为代码非常的简单,我把这段代码拿过来,好吧,这我相信同学们都能看懂,这是什么意思,给我说一下。隔出下,好,现在呢,我们来调用一下这个test的方法,看看它输出什么。我这写点注释,通过打印,打印问题回顾回顾。回顾什么呢?递归递归的调用机制,递归调用调用机制。好,同学们看我在这里太的一个什么呢?太的一个市。Pass的一个四,那么同学们先想一想,当我运行这段代码,它应该输出什么?
07:02
他应该输出什么?好,现在这样子啊,我们先不运行,我们先做分析,我先把这,呃还是老规矩,我们把这个Excel打开,我们来回顾一下这个递归的调用机制。好递归调用机制的一个讲解。对吧,讲解OK,好,现在呢,我把这段代码先给大家伙拿过来。这是我们的这段代码,对不对,我把这段代码呢拿到我们的Excel表。拿到我们Excel表好。现在我们来看看递归在我们的程序内部到底是如何调用的。首先呢,大家都知道,当我们的程序执行的时候,它首先进入到主方法,这个没问题吧,那么根据同学们在学Java的时候知道我们Java Java的这个虚拟机呢,它主要分成了这么三个部分。好,我在这简单画一画啊,首先第一个部分呢,就是我们所说的这个占占空间。
08:07
没有问题吧,那么这边呢,还有一个堆空间。这边是是不是我们的一个一个堆空间,好,我在这呢,也换一个颜色叫堆。好,另外呢,还有一个空间。啊,姑且我们叫做代码区。当然这边常量也是放在这的,对不对,常量也是放这的,这个呢,我们写个叫代码区。代码区,那么常量呢,也是放这儿的。好的好,同学们,那关于这一个简单的分区,我们就说到这,现在代码从这里开始执行,当我们的程序执行到主方法的时候,他会怎么做呢?它首先会在这个站里面先开辟一个空间,独立的空间。注意听讲啊,这个这个空间呢,我们姑且就叫命。它其实是一个站啊,从从数据结构来讲呢,底层它这个编译原理,它是用的是个站,它一旦是个站在这里面,它调用什么呢?调用test的注意看啊,同学们看它在这里面呢,调用了我们的test的多少是。
09:16
他一调用这个四呢,根据我们地柜的调用规则,它会干什么呀,它会立即开辟一个新站,待会儿呢,我们把这个规则再整理一下。好,我在这整理一下这个递归调用的规则,递归调用规则整理第一个当注意听这句话啊,当程序执行到一个方法时,就会开辟开辟,开辟一个独立的空间。空间啊,这个呢,我们可以认为就是一个站。是一个独立的空间啊,那这个地方他一看到这有个test的是它会干什么呢?它会开辟一个,开辟一个新的独立空间,也是放在我们这个大的一个站的这么一个数据空间的,在这里面呢。
10:07
同学们注意观察它,就相当于一下到这来,到这来,执行到这了,执行到这里呢,同学们看这个地方,这个N就是四,也就是说在第一次调用test的方法的时候,它这边会有一个变量叫N,是个局部变量,等于四。在这个事里面进去过后呢,它执行的是这一段代码。执行到这个代码呢,首先他会怎么做呢?他会看诶如果N大于二。怎么怎么样。否则怎么样,大家看,当N大于二的时候,是不是它又直行到。又执行一个T的N减一啊。是不是就形成递归,那这个时候它会怎么办呢?它会T的几压N减去一个1N现在在这个站里面是几是三,所以说这边相当于四减一。
11:01
等于几呢?等于三。当它执行到这个地方的时候,注意啊,同学们注意听听这句话,它下面的代码先不会执行,立即就会在这个地方又去调用站,也就是说刚才。刚才当他执行到T的时候呢,他开辟了一个站。他开辟了一个独立的空间,当他执行到太的三的时候呢,他仍然按照这个规则来走。这个时候又开辟一个站,这个站呢,传进来的N是三,注意这两个都虽然是N,但是数据空间是独立的,就是说你这个站的N是四,这个站的空,这个站的空间是几呢?是三是独立的。独立的它同样也进入N大不大于二,N大于二的话呢,又去调用这个N减一,当然这个时候的N减一是三减一。三减一其实就是二,同样的道理,同样道理啊,我把这个稍微的往上拉一拉,因为这个空间不够了。
12:01
好吧,我把这个往上挪挪一下,同样把这个赞呢。往上顶一下啊,不然的话我这没空间画了,好当他直接到这里的时候,老规矩,他刚才是在这个地方掉到这来了是不是。哎,那现在呢,老规矩,到这儿他又开辟一个站。注意听讲啊,开第一个站,那这个时候这个站传进来这个N是几呢?是二,也就是说在这个站里面呢,又有一个N的变量,再说一遍,在这个站又产生一个很N的局部变量,但是这个N呢,跟下面这些N不是同一个,是局部的,是独立的,OK,那现在呢,这个时候大家想一想啊,这个时候他进来过后,他会怎么办呢?来我们看一下。他仍然走啊,刚才这条线我们还把它刮起来。好,同样我们在这儿画一个线。那么这个时候它调用T的二进到这N等于二,N大于二吗?二肯定不大于二。
13:01
二不大于二在这个站里面,就是老师先说的这个站。我们标成另外一个关键的颜色吧,比如说标成这样一个颜色。诶,这个颜色还不行,标成什么颜色呢?要标成一个较深的颜色才可以。OK,他在这儿,那么他这个地方N2不大于二,它就会干什么呢?它就会出来执行,这个叫做下面这句话,也就是说它真正执行的第一第一个这个指令输出这个指令在哪里呢?在这里。在这个最顶顶层的这个站。最顶层的站,那同学们想,此时此刻这个N是几呢?二所以说它首先在我们的这个控制台就输出了几页,好,我在这儿画一个啊,同学们,因为我的空间不够了,我在这儿画一个。也就是说,假设这是我们的控制台。控制台,那他第一次输出的应该是多少呢?应该是N等于二。
14:03
个位N等于二,那也就是说当他把这个做做完了以后,其实他最先执行的是顶级的这战马最最上面这个,嗯,那么他把这个执行完毕以后,这个代码就结束了,就这个站,嗯里面的代码就执行了,结束结束完了过就就返回,返回到哪里呢?又返回到这个地方,也就是说他这执行完了过后,他整个这个站又回重新回到了。我们这个站。下面这一张啊,我用另外一个颜色描述又回来了。相当于他相当于这个站退出了嘛,因为执行完了这个站就没有了。就退出了,你可以这样理解,你可以理解成这个站。没了。理解我的意思吧,当然因为我待会儿要讲课,所以说我先暂时的,呃,放到这,你认为这条线就回来了,回来以后是不是他继续执行。我们的这个站,也就是我把它标成另外一个颜色,标成这这个颜色,同学们看一下啊,标成这样一个蓝色,它又执行这个站,这个站是不是它仍然把这个。
15:11
If,这个做完了以后,同学们是不是他也要执行这个system?能理解吗?也就是说他在这里面呢,这里面这个站也有个system,我这往下拉一拉。好,这个时候他应该输出几呢?N等于几呢?同学们,因为你在这个这个蓝色的这个颜色的站里面,这个N是三,所以说它会输出三。同样,当他把这个站执行完毕以后,他也要予以返回,也就是说他又返回到下一个,因为你这执行完毕了,他又回到。这个站这个站我换另外一个颜色啊,我换译成一个,呃,这个这个颜色吧,大家看要看的清晰一点,这个红色它同样回到这个站是不是,嗯,因为你你这个if服相当于test test三都执行完了,执行完了过后是不是他也执行自己的system。
16:03
是这意思吧,好,那这个地方画的有点有点不够啊,太太小了,画的有点紧张啊,画的有点紧张。呃,把这个字放小一点,好画一个九。这样大家看的清晰了吧,啊,它执行这边,那么到这个站的时候,它执行的这个输出语句应该是几呢?仍然是N等于几,N等于几啊N等于四,所以它会输出四。OK,当他把这句话执行完毕以后,这个红色的站也执行完毕,他又继续返回。返回到哪里呢?返回到一个主站,主站,呃,主站,其实这个因为大家也看到主站把,其实我们这个主站只是调用一下test。Test的这个四,呃,下面没有代码,当这个主站执行完毕过后,下面这个就干什么呢,就退出程序了。退出程序能理解我的意思吧,因为你下面没有没有其他语句了嘛,所以他就退出程序了,好相当于说把这个执行完毕过后,我们这个程序就结束了,因为主方法都已经全部执行完毕了,那就退出程序,好我这写到这啊,这就当这句话就退出了程序。
17:13
退出。退出诶这些啊,退出程序写到这就可以了,能理解我的意思,也就是说相当于说它反正返回到哪了呢,返回到这个位置是吧,返回到这个位置。返回到这个T的四下面没有代码就推出去了,那也就是说我们这段代码输出的应该是234。234能理解吧。能理解啊,那现在呢,我们运行一下,看看代码是否跟我们刚才分析的一样来运行值。诶,同学们可以看到,同学们可以看到完全一样的。完全一样的,那同学们我们再问大家一个问题,假设我这边做一个小小的修改,你们看输出什么,我加一个L。同学们,当我加了else,在这个test的方法里面,我加了else,请问。
18:02
我们这帮输出什么?我们输出什么?我加了L时,它输出什么?我不加else输出的是234,我加了else输出什么。输出什么东西吗?同学们想啊,我们还是回到这个图。你第一个你你你最终最先执行的是不是最上面这这个站。是不是这个站,我把这个站嗯换一个颜色吧,这样不好说这个颜色我也不知道个颜色是什么黑色吧,这个黑色其实你你们有没有发现真正执行哦,这个颜色还不好,就是就看这个吧,它它这个进入到if语句里面的。就是没有没有执行,没有进到IF1句的,只有最上面这个站,因为二不大于二,所以说它顶级这个if没有进去,它会进入到我们。这个里面的A,所以说N等于二还是要输出的。
19:00
N等于二还是要输出的,但是但是同学们,你的这个站,还有这个红色的站,其实你这这两个地方。独立的这个独立这个站,其实它已经进入if了,进入if else就不会进去。是不是,那也就是说,如果我们加了S,它的这个结果应该只有什么呢,同学们。如果是我加了加入了啊,加入了这个S,那么最后这个输出结果只有一个N等于二。大家能看懂了吗?因为你只有顶级进入到,没有进入if,所以它进入else,你这个已经进入if了,那else是不会不会进的,不会进的话呢,相相说另外几个站要是不会执行。对不对,所以说当我加了S,你会看到结果呢,只有一个就是什么呀,就是N等于二,就是刚才我分析的,当加了这个N,只有N等于二,不相信我们来试一下。
20:00
运行着。我们可以看到只有一个N等于二。好了同学们,那关于这个呃,递归的一个机制呢,我们就通过了一个打印来回顾,现在呢,还有一段代码,我们找一个同学啊,我们来一起想想这个阶层它的机制是什么样子的,来走一个。前面这个是打印问题。打印问题。好,那么打印问题呢,这加S和不加S是不一样的,我把这个注销一下。好,打印问题,如果在这个不加as的时候是什么结果和加了是什么结果,我已经讲过啊,现在呢,我们再讲一个阶层问题。阶层问题。好,同学们看这段代码,我先将起格式化。OK,那这个阶层问题呢,同学们可以看到它是这样子的,当你传进来这个N等于一的时候,它返回一,否则的话呢,是怎么样返回呢,是。呃,是让。
21:01
他调一个自身掉自己,然后呢,这传的是N减一。那也就是再乘以N,那么我们来看看他的这个结果,如果同学们看啊,我这样写system。我接收一下这个结果等于factoration。那好,如果我传一个一。他们想。同学一想啊,还是脑海里面还是要想刚才老师画的那个图。Res等于几呢?Res显然是等于一的,因为你传进去是一,它这一匹配等于一,直接返回就没有递归,所以说这样子呢,返回的就是一个一。对吧,那么如果我传的是一个二,同学们想它会怎么办?这个时候大家想象一下能力啊,如果它等于二,它首先不进入if,它进入else,进入else过后呢,这个地方就变成了什么呢?相当于变成了这样一个动作。二减一。再乘以一个二。是不是,那当然这个二减一它就算出来就是一,说白了就是它在这里面会递归,它这个factoration返回的是几呢?它在调用的时候,是不是调用完毕以后,返回的结果就是一,因此整个这个结果是变一。
22:13
是不是,那么最后这个结果变成二。也就是说这个时候呢,它返回啊,返回的是一个二。刚才是一,现在是二,你看那么你你看刚才我们把这个改成一啊。是不是这样子的。好,那么改成二,它返回的是二,同样其他道理我就不一个说了啊,如果你传递的是三,是不是在这个地方就会形成这样一个逻辑,它是怎么走的呢?那如果是三的话,它是这样子的,是三减一乘以几呢?如果是三的话,是三减一乘以一个三。那也就是说它到这个地方去二,那么FACTOR2进去过后,是不是又把它拆成两个部分,变成了什么样,是不是变成了这样一个结果,FACTOR1去乘以一个二。
23:03
那么最后这个结果是什么呢?一乘二乘三。等于六。明白我的意思吧,好,也就是说这个地方如果我们传的是三,那么这个结果呢,就应该是六。没问题吧,好,同学们,那这个,呃,这个递归的调用的一个机制呢,我们就先给同学们回顾到这里,我把它简单的板述一下,这个还是蛮重要的了,尤其是老师给大家画的这个图,一定要去理解这个图的一个调用机制很重要,因为后边我们讲迷宫问题,八皇后问题,都跟这个机制有密切的关系。跟这个机制有密切关系,好,那现在呢,我们先把这一部分给同学们板书到笔记中,刚才我们讲的是一个什么东西来走一个叫递归。递归,OK,没有问题吧,递归,那讲递归我们还是老规矩,首先我们看了一个递归的什么呀,应用场景,引起大家的一个思考和学习的兴趣,是不是有一个迷宫问题来引出的。
24:08
对吧,这是一个迷宫问题,然后呢,这有一个小游戏给同学们运行了一把。对吧,小游戏给他跑一遍,把这个小游戏说完了以后呢,我们给大家看了一下递归的基本的一个概念。基本的一个概念,那么递归的一个简单的概念是什么呢?可以这样理解,递归就是方法自己调用自己。就自身调自身,而且每次传入的是不同的变量,大家看看怎么理解传入的是不同变量,是不是从这个图就能看出来,第一次传的是四给他,第二次传的是三,第三次传的是二。是每次都不一样。对吧,OK,那这个说完了以后呢,我们又给同学们说了一下递归的调用机制。通过两个小案例来。回顾了一下地柜的调用机制。
25:01
好,哪两个问题呢,我们把它放这儿。OK,第一个是打印问题。第一个是打印问题,第二个题,第二个是它的这个阶层问题,对吧?好,那现在呢,我们把这把这个问题抛出来过,我们先先干什么呢?先使用图解。使用。使用图解的方式,方式啊,说明了递归的调用机制。图解的方式说明了递归的调用机制是什么样子,那这个图在哪里呢?图是不是就是刚才老师在这画的这个图,我们以打印这个问题来描述的,就是他是到底他是怎么做的,是不是看这里当程序调用一个方法时,就会开辟一个独立空间的站,第二句话我们再加一步,每个每个空间的数据啊,我们说的是局部变量,如果是局部变量,局部变量。
26:06
变量的话,那么每个空间的数据及局部变量是独立的。是独立的,你看啊,我们在这个红色的站有个N变量,在这个蓝色的,蓝色的站有个N变量,在这个绿色的站有个N变量,但是同学们发现虽然都是N,但是值是独立的。能理解这个意思吧,能理解这个意思,好,这是我们画的一个图,我把这个示意图呢给各位朋友板书到这里。好,呃,这边呢,我们一边讲一边还把递归的规则说了一下,这个图尤其重要啊,同学们,这个图一定要认真的去理解,哪个地方不明白一定要认真的理解,好,我把它换成一个叹号。很重要的。好,那把这个图呢,给同学们放到比喻中。最后我们把代码给大家阐述一下,就是呃,关于代码的演示,把代码放这儿,代码。
27:03
那刚才我们这说的四三就是四了,代码演示。哦,代码演示。对吗?也是。好,同学们,把代码呢,我就直接从这个位置给大家放在笔记中就可以了。好,各位同学,那关于递归的应用场景和调用机制,先简单的回顾到这里,待会儿呢,我们来继续说。
我来说两句