00:00
好,那么关于方法这块的话呢,我们还有一个点就是叫做递归方法,哎,我们把这个递归方法呢,给大家呢,稍微讲一下啊。好,那什么叫递归方法呢?啊,这就提到一个递归这个词啊,一说到递归的话呢,这我放了几张图啊,看大家能不能看得懂是吧。哎,在这个图里边也有这个图啊,这个图里边有这个图啊,所以就是大四大概呢,就是这样一个效果啊。这个好早之前的时候啊,这个我在微博上啊,看到过这样一张图,当时觉得还挺浪漫的是吧。哎,说呢,这是他俩呢,最初的时候在一块儿,然后照一张照片,然后每年呢。啊,纪念日的时候呢,都会照一张照片,他会拿着之前的这个最近的照片呢,会照一张是吧。哎,显得非常的有意义啊,这呢,其实有点就像那个递归的意思一样。哎,后来一不注意发现呢,这个转发的这个呢,好像也有很多人都转发过,也像个递归一样是吧。嗯。好,这是一个例子了啊,诶另外一个例子呢,就是说以前我们讲了一个故事啊,诶古代有座山啊,山上有座庙,庙里一个老和尚,老和尚给小和尚讲故事,讲的什么呢?啊,又是这个事儿啊,哎,一直呢就下去了,这个事儿的话呢,必须得有一个终止啊,如果没有终止,在我们程序当中每一个如果看这个方法,方法呢,无限的自己叫自己。
01:12
那最后呢,就会出现死循环是吧?诶我们程序呢,是不能出现这种类似于死循环的结构的啊,所以呢,最终呢,一定得有个结果。是吧,没有这个结果呢,就不行了啊,结果老和尚没了,庙塌了,小和尚还俗了是吧?啊,这个得能出来这个。递归啊才行。好,那么我们这块呢,说一下到底什么叫递归方法呢?诶其实呢,就在方法里边自己调用自己的这种现象,就称为呢叫递归了。这个我们把它呢拿过来。哎,咱们前面讲过,说方法内可以调用方法。那方法内呢,如果调别的方法呢,那就调别的了,如果自己调自己,哎,我们就把这种情况呢,称为呢叫递归方法调用。哎,其实在以前我们见到过递归方法了。在哪儿啊?
02:02
哎,讲数组的时候啊,数组化呢,我们讲过这个具体的数组的排序。诶,常见算法里边的,诶在这块有排序,排序里边的话呢,我们提到了叫快速排序,快速排序啊这呢,我们调的是这个方法,这个方法里边呢,这不我们封装到一个叫sub sort里边了,那么在sub sort里边呢,我们发现自己又掉自己了。哎,这不就是递归吗?啊,因为呢,我们呃当初啊,稍微回忆一下啊,快排的时候呢,我们找到一个呃P沃是吧,叫个轴也行哈,然后呢,把后边的元素呢,分成比它小的和比它大的。然后分完以后的话呢,它可能就在这儿了,诶分成前后两个了,前后两个的话又得是找到诶直定力元素比它小的比它大的,这不是每一个呢,操作的套路都一样嘛,所以我们就分成了这个叫,哎,自己里边掉自己这样一种行为了,这呢就是叫。递归方法。OK啊,其实呢比较好理解,那么递归方法的分类呢,啊,这个分类的话呢,我们就分成了这个叫直接递归和间接递归。
03:01
哎,这个我们就直接拿过来啊,哎,其实呢也比较简单,直接递归呢,就像我们刚才看的那个快排一样,直接就在刺激里边掉刺级了,叫直接递归。啊,类似于这样的结构啊,那么间接递归呢,就是A里边掉BB里边调CC呢,调A了。啊,类似这样场景就是你猛一看呢,好像不是地归。但是其实呢,你在放眼比较,诶,更更更高的一个角度来看的话呢,其实最终还是出现了A调A了。诶,所以还是一种低贵。啊,就是这个呢,叫间接递归啊好,那么下边呢,是关于这个递归的一个说明,那我们看一看这个其实大家也都比较好理解啊。看第一个啊,生产递归方法呢,它包含了一种饮食的循环。你像自己里边掉自己,自己里边又掉自己,哎,这就是一种隐视的循环了啊,它会重复的执行,哎我们方法体的这个代码,哎这种循环的话呢,我们没有使用循环结构。啊,这是这样一个场景,好,我们前面讲循环结构的时候呢,提到过,说要避免出现死循环,那么方法调方法也是同样的道理。
04:07
说一定要向着已知的方向去递归,否则呢,就会出现无穷递归,无穷递归停不下来了,就像死循环一样。啊,那最终呢,就会导致叫占内存溢出啊这样的一个特点。OK,行,那说到这儿的话呢,咱们就简单的来去写个代码,去体会一下这个递归方法的一个调用情况啊。啊,这个咱们把上面这个呢,就都收起来是吧。来来这儿啊,递归啊。这个递归的话呢,用这个英文呢,叫reccusion啊。啊,Cusion这个递归的意思啊,好嗯,在这里边的话呢,你比如说啊,咱们把这个may方法我先放这啊。诶,在这呢,我们先简单的写一个这个方法啊哎,Y,比如说这呢叫METHOD1。这呢,我写个输入语句是吧,知道method。哎,这个方法好,那么在这个方法里边呢,我自己要自己了。哎,其实呢,从格式上来看,这就是递归方法了。
05:03
那这个方法呢,我们在这个main方法里面呢,去调一下啊,首先呢,得创建当前类的对象啊。诶这么着是吧,诶T点调一了啊,自己调自己提调自己,然后呢,诶其中我们所谓的说某端代码会重复的执行啊,其实在这儿呢,就是它。他不断的执行,然后自己呢又掉自己,那如果画这个内存结构呢,它就出现了,诶我们main方法里边掉了一个METHOD1 method1呢还没执行完呢,又自己掉自己了,自己呢又掉自己了。嗲嗲嗲嗲。而且呢,没有所谓的这种终止是吧。哎,那你这个占空间呢,总有一个大小啊,那你无限的掉下去的话呢,总会出现溢出的场景。所以我们一去run。哎,这个呢,就会出现这个溢出的这个问题。往上拽在哪呢,啊过了。A,好在这儿是吧?在这出现了啊,说叫stack overflowed啊,这就是战役出的一个错误啊。
06:05
哎,我们在这就写上啊,那么这个操作呢。哎,如下递归。诶,方法的调用啊,会导致。诶导致,诶我们这样的一个错误信息。啊,行了,这个呢,就是我们体会一下这个场景,行,这个咱就不在这儿去调它了啊。好,这个呢,我相应的给大家注释一下,好,那么这种呢,显然是不是特别靠谱的,但是递归方法本身的话呢,是可以解决我们很多的问题的,比如说现在我们就写具体这个需求啊,诶举例一。哎,举例一呢,我们想做个事儿呢,就是叫呃,计算啊,一到100内啊,自然数的和。哎,自然数的总和啊好,那这块我们就是希望这样子的,哎,你把这个结果呢给返回一下啊,这个我们就叫get sum了,哎这呢我们想计算一下指定的这个数,哎,你就从一开始一直到这个数啊。
07:00
好,那如果我们要不用递归的话呢,其实用循环也能做吧。对啊,比如我们这里边第一个some是零是吧?嗯,咱们写一个for吧。In,这个I呢是一啊,I呢小于等于sum啊,I加加。哎,在这里边儿呢,我们让这个萨呢加等于I。哎,然后循环完了以后呢,Return一下。就行是吧。哎,这个呢,就是我们用循环来去实现的啊,稍微看一下。诶,这个我们写个100啊,返回的结果呢,咱就直接打印了。Run一下。零是吧。啊。哪写错了?循环是一小等于它。啊,这哦哦对这这这写错了是吧?对number哈,对I小于等于number啊OK。哎,行这个呢,我们就出来了啊行,你像我刚才这块呢,我写错了,写错以后的话呢,怎么排呢。
08:03
这是咱们所说的啊,你看这个程序运行的话,也没出现最终的一个错误信息是吧。没有出现错误信息,这个其实是比较恶心的,哈A也不报错。然后呢,你说这块从哪看。黄色的,黄色这个有的也不靠谱。啊,这个还真是写了一个是吧,哎,但是这个不靠谱啊。啊,就是有的时候呢,他不会都会给你提示这个黄色的,你想编译器得多强大,还得给你提示一个叹号是吧。哎,OK啊,哎不一定都有啊,那怎么办呢?诶这个呢,比较low的办法呢,就是硬看是吧。那你就从往后一行啊,你就去分析是吧,但是你有时候看着看的话呢,脑子就已经开始打转了是吧,就懵了啊,所以呢,硬看这个事儿不靠谱,尤其呢,当代码量比较大的时候呢,就更不靠谱了。怎么办呢?诶以后我们会讲这个debug啊,诶咱们讲面向对象呢,到最后的时候,咱们给大家讲讲debug,包括呢,这个常见的,呃,这个快捷键是哪些,咱们统一的讲一讲啊debug呢,就是你这块点一个这个红点,然后我们去运行的时候呢,就可以走这个叫debug模式,就这个代码就一行一行去走,我们看每一行诶得到的结果是不是都是你想要的。
09:09
哎,出现一行不是的,那那这块就有问题了啊,后边我们讲啊。好,这个改完之后呢,刚才也运行了没问题,那我们呢,也可以考虑呢,使用这个递归呢去实现。哎,这个我叫get some,哎,这个咱就换个名了得啊,In number。好,那么这个递归呢,咱们看看怎么做啊。所以呢,我现在想计算一下100以内啊,自然数的和,呃,那这块的想法就是说,如果我要是计算出来了。就是一到100的和是吧,如果我要是计算出来了99的一到99的和了,我使需要呢,拿它是不是再加上100就行。哎,那么它的话呢,是不是就依赖于说呢,只要我计算出来了。对,Get some这个98的了。我再加上一个99是不是就行。那以此类推啊,到最初的时候呢。哎,是不是就到这个get some。
10:02
一把。啊,一的时候呢,它不就是一吗。一到一的和就是一是吧。然后一要算出来了,我们get sum2呢,是不是就是你get sum一再加上一个你这个二本身这个数就行是吧。所以你看我这样写哈,呃,就是大方向的话呢,我们是想这样做了,让那个number呢减个一,然后再加上你这个number。对吧。诶这不就是,诶相当于自己呢,就调诶干萨一是吧,诶这块呢,不就自己呢,就调自己了吗。好,但是这个事儿的话呢,诶,我们走走走走走,你最终呢,我们说得朝着一个已知的方向,或者说你得有一个终止的一个情况啊。这个中日的情况呢,就是如果这个number呢。是一的时候是吧。它是不是就是一啊。诶,如果他要不是一的话呢,我们再走这样一个关系式。你看。看这个能不能行。你看啊,如果呢,我们这个就是一。
11:02
是不是就返回一了是吧?哎,如果是二呢。没走这儿走这儿了,Get sum2减一,是不是get sum1,再加上一个二,然后这块呢,Get sum1的话呢,我们是不是就回去调自己。掉自己的话呢,是一返回的是不是就一了,哎,是不是变成一加二了吧。对吧。这样啊,好这块呢,大家可能稍微的啊,有点转不过来,你看一下我这里边儿这个课件啊。课件我举了个这样的例子,就是这个数稍微小一点,我现在是计算前五个数的和啊。哎,Get sum这写了个五,这呢不跟咱们刚才写的这代码一样吗?没问题是吧,好看着啊,我在这个may方法当中,这是咱们的没方法,然后我定义这个N呢是五。然后呢,调这个get sum这个呢,不就是五吗。Get萨姆五这块我们就出现了一个战争,就是盖萨姆五这个方法的一个调用,啊,这个N呢就是五了。所以呢,你调这个方法的时候呢,这不是return就走的这个哈,就是五加上get sum5减一,这不就四了吗。
12:05
诶GET4SUM4这个方法啊,又掉它了,这呢又重新加载一个get sum这个方法。这个里边这个N呢是四。诶四这块呢,就是四加上这个四减一嘛,哎,又掉个新的方法,这块又再去,哎加载一个战争。诶还叫盖这块呢,是四减一这三了哈。三再加上GET3减一,这个就二了,然后再调你新的get sum2。啊,N是二了啊。嗯,二呢,再加上get萨姆二减一是1GET萨又掉这个参数,这个是一了啊,再去加载一个get sum。那一的时候呢,这个呢,就走的是这个衣服了,所以就是一。所以呢,诶到此为止了啊,到这个时候呢,我们这个方法呢,就算是执行完了,他没有再在这个get sum里边再调查自己了。所以呢,这个方法执行完以后呢,它就返回了一个一吧。对吧,诶我们前面讲过啊,说方法调用完以后呢,这个return返回一个值,返回给它的调用者。
13:04
谁教他的?没没,那是最最后的哈,他掉的吧。你不是在这个里边调的这个吗。所以谁掉呢,是不是下边这掉的,所以所以他就把上边这个结果的这个一呢,就返回给你下边了,所以这个结果呢,整个的就一嘛。啊一你又加上这个N是二,二加一是三,Return就变成返回一个三,诶这个方法呢,就返回给它的调用者。他调那是不是就下边这个。诶,所以就返回到这儿了,那这个结果这不就三了,三再加上前面这个三,诶这就变成六了,然后这个方法就返回了,又又弹出站了,又弹出站以后呢,这就是六,诶它就给它的调用者就到这儿了,这再加上它以此类推,以此类推,这不就最后呢,我们就回到这儿,把这个结果就算出来了吗。那么前边的话再捋一下啊,我们在may方法里边调该萨姆,萨姆又掉它又掉它又掉它,这个呢,一个一个的站着往后垒,垒到一定程度的时候呢,这个就到头了。然后呢,接着呢,他执行完以后呢,就依次再返回,返回又回来了,这个就是依次呢,就出战出战出战出战,诶最后就到这儿了。
14:04
哎,就结束了。哎,这个清楚吧。哎,这呢,这不就是自己调自己调自己调自己朝着已知的方向进行,最后呢,有一个结束,然后呢,又哎都出战出战出战再回来。好体会一下这个操作。好,那这块呢,写完以后呢,我们在上面呢,再去做一个调用啊,咱们叫get sum1嘛。哎,做一个rap。哎,还是那5050。那说明我们这个计算呢,是没有问题的啊。OK,这呢,算作是咱们的第一个例子了,然后接着我们再举个例子啊。举例二啊,所以呢,我现在呢,去计算一下这个叫N的阶乘。这个咱们上高中的时候呢,接触过啊。哎,获取这个阶层。啊,这个咋去算呀。哎,这个我们还返回in的是吧,哎,Get它的这样的一个结果,哎,这个multily是个成绩的,我就这样简写吧。
15:01
哎,印了一个N啦。哎,那你说我这块里边怎么设计。衣服。N等等于一是吧,哎,是不是还是一呀。好,然后else。来return一下。嗯,N呢,去乘以一下get ma n减一是吧?哎,这不就可以了,其实就是上面把这个加号换成乘号就行是吧。那就可以啊,行,那我们来做一个测试啊。啊,单一下get一个,哎。哎,Test是吧,点get一个这个帽啊,诶这个呢,咱们给大家整的小一点吧。比如整一个五的阶乘是吧,这样我们就来一个五就行了啊。这个你自己得算一算。一百二啊,这么快啊。一百二是吧,好,那么这个过程呢,你看简单的一个图呢,我这也画了一下啊,那你要算五的阶乘,它不就是对应到这儿呢,就是五乘以四的阶乘。啊是吧,然后呢,这个接着往后拆拆拆拆拆拆到最后呢,就是呃,一再结成就是一了,然后你再翻回去啊一串再回去就行了。
16:08
哎,这个递归的一个过程。哎,递归的一个过程啊,行,这个呢,就是我们说的这个第二个一个举例哈,哎,然后呢,第三个举例。哎,这个咱们讲的就是诶快速排序嘛。哎,这呢,我就不往这放了啊,诶方法自己里边要自己我们实现一个排序的操作啊,这是快排的一个事儿了啊,哎,这个我们就列了啊,然后呢,还可以呢,比如说举例。呃,举例四,就我们见到的一些具体的递归的场景。啊,这儿呢,我再写一个。啊叫诶汉诺塔。啊,游戏哎。游戏啊。哎,这个啊,嗯,这个大家玩过不。没有啊。那是因为现在这个游戏都比较高级了,大家都玩那个RPG的那种,玩这个什么策略性的是吧,王者呀,王者荣耀啊等等这种哈,以前的时候我们上这个中学的时候呢,那时候用那个文曲星是吧。
17:04
闲的没事的时候就玩一玩,因为那里边儿游戏呢,比较。就对它硬件不是比较差嘛,是吧,所以呢,玩的游戏都比较简单,里边呢,就典型的就这汉德塔了。啊,还有那个五子棋啊,啊这种啊扫雷包括啊。这个汉州塔它是这样的啊,简单的稍微的说一下,有同学可能知道啊。对,还有三个这个杆儿是吧。嗯,三类杆的话呢,说嗯,这叫ABC吧。嗯,简单一点的话呢,我们就就一个哈,这是最简单了,说呢最终目的呢,我是要把A的这个里边这个有几个这个里边套了几个这种。通讯的这个环是吧,呃,你把它移到这个C杆里边,呃,一个的话呢,你就直接放这就行是吧,两个的话呢,就是我先放的是这样的,小的上面,大的下边。然后要求你把它放到C的时候,也得是小在上面,大的下边,但是你在移的过程当中呢,你不能出现这个,比如说我把小的放下边了,大的放上边儿了,这种是不允许的。
18:06
中间你可以借助于B。那两个的话比较简单,你就把。下面这个你先放这儿是吧。这个放到嗯,这个小的放这儿,然后你再把下边这个呢,是不是往这一放,再把这个拿过来,这是就可以了。哎,这个呢,是两个的这个情况啊,哎,那么三个呢。呃三这呃咱就不用继续放了啊,这个呃下来研究研究啊,就是我想说的什么呢,就是你看三个也好,或者我们三个会也话呢,再来个四个的是吧。哎,那么这个整个在放的过程当中啊,我说其实里边会出现这种递归的场景。啊,你看我越来越多越来越多,你呢就可以怎么着呢,我这呢,是不是放四个是吧,四个放的时候呢,我可以考虑呢,把这四个呢,我看作是呢。两部分,一部分呢是这个,一部分是下边这个。我想放四个的话呢,那我就先考虑,比如说放三个的。
19:01
是吧,哎,假如我在这里放一个,是不是就三个的,三个的要放成了四个的,不就是在它的基础上,我们就多了一个这个而已,你再想考虑,再想个办法,就把这三的再怼上去不就行了吗?所以说呢,我们四个呢,依赖于三个的,放三个呢,依赖于两个的,放两个呢,就比较简单了。啊诶,所以呢,就又会出现呢,在诶我们放在这个规则里边,自己调自己这种场景。啊,那这呢,其实也是一个递归的实现。OK啊,诶这个我们就不写了,这个写得花点时间了,大家呢,你可以在百度一搜汉诺塔空格Java。诶,那么就Java的这个实现的这个汉诺塔这个游戏呢,就给你写出来了,然后里边呢,针对于每一个,呃,这个块你怎么摆怎么摆,从这里边放这儿,这个放这儿,诶你按照那个规则呢,去整,他就永远都错不了了。所以呢,给你放到七个八个的,呃,可能咱们整就不好整了,但是一旦呢,要给出一个公式来了,你就按照这个公式呢去操作,它就永远错不了。哎,也是一个递归的实现。OK啊行,这是一个场景,然后呢,再接着啊举例。
20:03
哎,举例五是吧。这个大家呢,有没有听说过这个叫北们纳切数列呢?嗯,飞波。嗯,拿起数列是吧。这个满足这样特征的这个数列呢,我们就称为呢叫费纳切数列了,费纳呢是一个人名是吧。OK啊,什么样特征呢?第一个是一。第二呢,也是以。诶之后的话呢。对之后的话呢,哎,这个数值呢,就等于前两个数值的和。所以在幺幺二三五八十三二一三四五五加点啊这样啊,为啥我这计算这么快呢。呃,因为我家的那个无线路由的WiFi密码呢,就前十位。到这儿。啊,所以他们一般过去的时候说是你家WiFi多少,我说就费纳切数列的前十位啊。显得很高大上是吧?
21:01
哎,虽然说呢,这个呢,纯数值的,不是说不如那个什么大小写的中英那个英文的数字的。那个安全是吧。但是我就要一格是吧,嗯。对啊,哎,就这个啊,这叫斐布那这数列了啊,你看这个数列呢,其实它就是用递归了啊,如果呢,我们用呃,这个F来表示这个所谓的这个方法的话啊,它不就等于。当然一一般的一个公式啊。减一的是吧,再加上这个。减二的是吧,对,当然这个呢,你注意一下,最开始这俩不太适用。对,这个N呢,它得大于N。大于二是吧。大于二是吧,那一和二的时候呢,都作为这个特殊的值出现是吧。就是你要写的话呢,这个是不是也能写出来。哎,我就写成in一个N了是吧。这个怎么着,If n是一。哎,个一是吧。啊,N呢是二。
22:00
还是一是吧。嗯,Else。这就这个了。诶,是不是这样就可以了。OK啊行哎,然后呢,如果呢,你要说我这是想第十个十级,那这就往这一套,这就出来了,这呢我们正好第十个55是吧。嗯,在这测试一下啊。在最初这儿。啊一一个啊,按in的一个M,比如说这个呢,我们来一个第十位呗。t.F把这个M呢往这放进去打印一下。哎,这不55吗。哎,这样就行啊,OK,那么那个斐文纳杰数列呢,呃,它其实呢,这也是一个递归的一个操作了。哎,这就过了啊好,然后呢,诶,我们可以再举一个例子哈。哎,这个举例六,哎这个呢,还是就没有这个代码了,但是这个事儿呢,我一说呢,大家应该就明白啊,后边呢,我们会讲这个L流,哎在IO流这块呢,我会讲一个类呢,这个类呢叫做file类。哎,用这个file类呢,哎,我们它的一个对象是吧,可以呢,表示一个文件目录。
23:06
那我们可以呢,去获取这个文件目录,它的一个大小。哎,获取文件目录的大小啊,其实这块呢,就跟我们平时的这个操作呢,是一样的啊,你比如说诶针对于我们这个吧,这这个文件目录了,诶我这个文件目录的话呢,后边我们会讲啊,我就拿file这个类的一个对象呢,来表示对应的路径呢,就是诶比如说D盘下的到这个下边的诶这个。哎,就他这个路径好,咱们平时的话呢,一右键是不是可以点属性,看它的所谓的大小是吧。哎,那么其实这个大小呢。它是怎么算的?是不是就把你这个文件里边的所有的文件都大小都加起来就可以了。哎,当我们这个文件呢,比较深的时候呢,大家其实应该也有过这样的经验,你再去看大小的时候,你会发现这个数值它。一直在变是吧?哎,然后最后给你算这个数,那这个变的过程,其实就现在呢,不断的跟你去在做计算的过程,其实这里边儿呢,又出现了递归了。
24:03
啊,它是这样的啊,就是正常来讲,它不会说有一个现成的一个,你说一个属性我一点,诶,立马就在这个内存中或者磁盘中写着它的长度,呃,这个大小没有。他只是呢,能够记录一下每一个具体的文件的大小,你看就跟这儿一样哈。这个文件的大小呢,是非常容易的就能够计算出来的,就是或者说你看到这个属性是现成的哈,但是呢,你里边可能还有文件目录啊。在这个文件目录里边,是不是接着进去。那进去之后的话呢,里边还有文件目录,是不是又接着进去,这里边还有文件目录。一直往里边走,所以这块呢,如果说诶我们现在呢,想计算,哎,我就举个例子啊,想计算这个文件目录的大小,我得是不是把它里边这个东西都得遍历一下是吧。这就好多个了,哎,那有可能这两个呢是文件,那就直接就计算了,但是呢,这几个呢,又是文件目录。是不是又得去便利?呃,然后里边有俩文件,然后这又是目录啊,又得去便利啊,下边又有以此类推,那这儿呢,我是便利他的。
25:03
这个文件子文件或子文件目录,呃,如果他要是个文件目录的话呢,又得便利它的子文件或子文件目录,如果他要是文件目录,又得如此,是不是每个里边都会类似的这个操作。就是便利它下边这个文件或文件目录都是重复的,所以这呢,是不是又是递归了。诶,这个咱们后边呢,到时候讲哈文件目录,然后呢,我们去呃计算。啊,叫指定的文件目录的一个大小。需要呢,不断的去递归。哎或者这呢是一个需求,还可以呢,去计算,哎或者哎不要紧,便利吧。哎,便利这个指定的文件目录中的所有的文件哈。那你要是你里边是个文件目录,还得再往里边走。啊,那也得是一个递归。诶或者说呢,我们还有一个叫什么呀,叫删除。诶,指定的文件目录。大家记不记得咱们第一天讲课的时候呢,咱们说过那个RD是吧。
26:04
2D删一个文件目录,但是那时候文件目录要求得是。空的是吧,对,你要是删除一个文件目录,它不空怎么办呢?你得进去。删里边的文件,如果里边还有文件目录呢,再进去是吧?啊一直到里边呢,真的没有文件目录了,然后把文件一个个删掉,然后退回来,把文件目录删了,然后呢,再退回来。哎,这不又是递归吗?哎,所以这呢,都是递归的这些行为啊。好,那么这样的话呢,咱们就举了一些具体的例子啊,讲到file的时候呢,我们到时候把这个代码呢,可以写一写啊。行,那么关于题归呢,咱们就哎说到这儿啊,那么这个描述最后给我们的启示是什么呢?我这下边呢,还写了这个题目,大家下来看看就行啊。启示是这儿大家你看啊。诶,我把这两个呢,CTRLC啊粘过来。哎,放到咱们这儿吧,哎,我写成是一个注意。这样啊。嗯。
27:00
诶,你看这个意思啊,首先说这个递归调用呢,它会占用大量的系统的堆栈啊,内存耗用比较多,在递归调用层次多的时候呢,速度呢,其实你会发现比循环结构要慢,所以呢,我们递归的方法呢,要慎用。诶什么意思啊,你看咱们刚才呢,在前面计算一下100以内自然数的和的时候,如果我们要用放循环呢,其实呢,就是你这块不是有一个这个具体的这个战争呢,是吧,战争里边这块定义个变量I,这个I的这个值呢,他就自己在这变就完了。啊,你要是用一个递归呢。你想他对于这个占的消耗啊。整了一个方法是吧,方法里边又调自己自己又调自己自己又调自己来说这里边儿,诶,我们这个可能会有新的变量是吧,这是一方面,另外呢,除了这个变量之外呢,其实这个战争里边存的东西还挺多的啊。还有这个,呃,操作出站呢,呃动态链接呀,链接就是你这个,你这个东西对应的是哪个方法呀,还得指向方法区里边那个方法的那个地址。啊,有的还有返回值地址,就这里边信息量其实挺大的,你要这样呢,一个一个的这样去整几千个方法的,自己要自己那就出现几千个战争了。
28:08
那我们不如呢,这个变量你在那自己改自己是吧。显然呢,这个用循环是不是效效效率是不是要更高一些是吧。哎,所以尽量呢,我们往避开这个递归的调啊。哎,它呢也比较耗内存。正好有的同学觉得说我正好,反正用它也不熟,我还是用循环挺熟的是吧,诶那你就用循环挺好的啊。好,这是我们说的它,呃,然后顺带呢,这块咱们有两个这个课题哈。好,那么关于这个递归方案这个后题呢,我们稍微的看一下啊,诶这呢先是有两个啊,这两个呢,我们直接CTRLC一下啊,去新建一个啊。是它的一个练习评议。哎,你看这个需求呢,是这样的啊,我就这样粘一下了。哎,这样注释一下啊。好,先来看这个第一个题目说呢,以这个数列F20是一,21呢是四,哎,有这样一个通用的关系式,现在呢,哎,让求F10。
29:08
啊,你得借助于给的这两个条件啊,你看我们这个关系是怎么去处理的。特类型的是吧。复方呢,我就叫我叫F1吧。我叫F也行,就用他这个给的这个名了啊。嗯,我这儿呢,就是一个int的一个N是吧。嗯,给的这两个条件呢,我们比较容易写出来啊,当你是20的时候。嗯,这个就是一是吧。当你是21的时候。哎,就是四没问题啊。好,接着else。呃,那么这块呢,看看咋处理。嗯。这块呢,注意我们要朝着已知的方向去走,是吧。已知的方向去走,诶有的同学呢,会这样说,哎,你看啊,我现在就要计算FN的啊,这fna不就等于这个减这个吗?是吧?哎,先写出来啊,就是FN加二减去二倍的FN加一。
30:14
然后呢,就是这个减这个不就等于FN,就你这FN是吧,这个你写完之后你得看一眼啊。比如说现在呢,咱们要计算的是十是吧。这个不对,这个不对,就进到这儿了,诶我得需要呢,依赖于F12减去两倍的F11是吧,那12呢,是不是不知道。12呢,再进去它就依赖于F14。我就逗号了啊,跟13吧。哎,真的依赖于。是三和。12是吧,那这个呢,是不是都不知道。哎,再接着往后走,你发现这个数是不是越来越大。哎,最后呢,是不是就靠到这儿了。哎,这就是所谓的我们说叫朝着已知的方向去走了。也就是说这个题目呢,这样写是对的啊,诶怎么样就错了呢。
31:06
啊,错误的啊。哎,有同学说呢,诶,我把这个左边呢,我看成是FN的话呢,它不就相当于是就等于二倍的FN减一是吧,再加上F。An,减二吧。就我把这呢整个看成FN是吧,就等于右边这两个,哎,这个相加是吧,这个其实就不对了。对,你看啊,你现在需要计算F10,你发现呢,它等于二倍的F9是吧。再加上这个F8了,九八不知道是不是再接着算九呢?依赖于八和七是吧。哎,以此类推,你发现这个数越来越小。越离这儿越远。哎,所以呢,这个就没头了,就算不出来了啊,诶这个呢是一个正确的。哎,这个注意一下,把这个打开。哎,这个呢,就是我们这个。哎,递归啊方法的一个编写,哎测试的话呢,比较简单,你把这个往那一写十是吧,哎就给你算出来了啊。
32:05
好,这是第一道题,然后看这个第二题啊。哎,第二题说呢,已知呢是F0和F1。诶,观音室的话,你看跟上边是一样的,还是F10。这个你就得看一下这个方向了是吧。哎,Int类型这个我们叫比如放吧。还是一个N啊。诶,他给的这个条件呢,你可以先写出来。一是吧。N呢是一。诶四诶没问题啊好,这时候呢,L看这了啊。对,这时候你要是再说HFN,我就等于这个这个。这个事儿你就得小心了。哎,减去啊两倍的。诶你看这个事儿呢,就我们刚才上面说那个错的事是吧,这个你要计算十的话呢,你要用它,这依赖于这个就成12。
33:01
呃,这个这是11了,然后十二十一呢,又得接着走,是不是越来越大。哎,那你这个是往小的方向走的,所以这个关系式呢,是一个错误的了。把这个得注释一下。诶,正确的啊,哎,这时候我们得怎么着啊。诶把这个呢看作是。FN是吧,哎,所以呢,它就是二倍的。啊,对,N减一再加上。啊,对,N减二啊。得这么着了。哎,这时候你要计算十的话呢,这不就依赖于九是吧。呃,九呢,加上这个八,哎,它呢在依赖于八和七,它依赖于七和六啊,越走越走越小,哎,最后就走到这儿来了。哎,这得给俩哈,因为你最后你要算的时候呢,它不得依赖是谁加谁,这俩是相邻的俩是吧,相当于这俩的话,你得有两个这个哎已知的条件才可以的啊。
34:00
行。OK啊,这呢,就咱们这样两道练习题,这个我就不具体去在这写,没方法去测了啊,诶大家呢,自己测就行了,好,这是我们说的第一道问题啊,第二道问题。啊,这个叫不死神兔啊。这个呢,其实就是经典的这个费拿起了。说呢,这个是他,呃给了这样的一个场景,哈,说这块呢,呃在他的一部著作里边提到了一个有趣的问题,说呢有一对刚出生的小兔。这个栏有个图。一边说呢,一边看这个图啊。哎,现在有一对儿呢,刚出生这个小兔说一个月以后呢就能长大,所以说一个月以后呢,就还是这一对儿。就长大了啊,然后再过一个月呢,他就能生下来一对,所以再过一个月呢,就变成两对了。啊,一对还是他一对呢,是刚出生的。然后此后呢,每个月都会生一对小兔,所以他就一直在生,他自己还可以生啊,每个月生一次,每个月生一次,每个月生一次。除了他能生之外呢,他生的小兔过一个月之后呢,又长大了也能生。
35:03
一想感觉这个好像就少不了是吧。啊对,就一直往下升,然后生出来这个隔一个月之后也长大了,也接着生。啊,然后问啊说这个两年以后哈。一段兔子。哎,就这样一个问题,哎,这个问题呢,其实我们发现呢,这就是一个非纳切的一个问题了。啊,这个呢,我们可以这样啊,这个咱们以这个月份来写这啊这个呢,就是兔子的。对对数是吧。兔子。Woods。兔子对数啊。好,那首先比如说第一个月呢。是一对儿是吧?往这发一下啊,然后第二个月呢。还是一对。诶,咋差一个呢。呃,第一个月呢,因为他还是这个这个小兔呢是吧,诶然后第二个月的时候,它长大了,还是这一对儿,然后诶第三个诶第二个月是吧。
36:00
诶,第三个月。往前整一下啊。诶,第三个月的话呢。两对了。然后第四个月。第四个月这就成了三对了是吧,这呢你第五个月。哎,这个呢,就变成这能是不是五对是吧。上面写对吧,一月二月三月四月五月啊对着啊。哎,这么着啊,哎以此类推啊,就往后走,哎最后呢,你发现呢,这不就满足这样一个公式了吗。哎,这个公式呢,其实就我们说这个斐拉契的这样一个公式了。啊,这个公式呢,其实就是这道题的一个做法了,咱就直接来写了啊。哎,兔子呢,叫rabbit是吧,哎,关于它的一个练习啊。好,这块呢,我们返回这个int啊叫get rabbit的一个是吧,这个是对对的意思啊。
37:00
这个呢,咱们就写个叫吧。啊,月份啊。好,那我们刚才发现了啊,所以呢,当你这个month呢,是。一月的时候是吧。哎,就这一对吗。Else if啊说这个month呢是。二月的时候呢。也是一对是吧,呃,然后剩下的else。哎,这不就我们那个关系式就出来了哈,哎,Get rabbit的一个number。啊,这个呢,减个一是吧,哎,再加上。哎,对这个,哎。哎,减个二,哎,这就可以了。好,那这个关系式出来以后呢,我们就可以呢,做这个测试了啊。哎,这么着是吧,然后诶,他第二我们去get,刚才提到说这个第24个以后呢,变成多少了。在这是吧。然后呢,诶,我们定一个month。哎,这个是24啊,哎,我们把这个24呢往这一放。
38:02
哎,这呢就多少对了,打印一下。哎,兔子的对数为。这是对数,不是别念成对数啊。指数对数,因为不是那个啊。嗯。哎,哇,这么这么多是吧。这个有点恐怖了哈。对啊,行,这个呢,就是我们这道题的一个具体的做法。所以这个有点夸张啊。有点生物入侵了,看这是吧。嗯,诶,所以呢,总开玩笑说这个哪块呢,这个。生物这块呢,如果长得太快了,我们只需要呢。让中国人过去就可以了,是吧?啊,中国人呢,是都可以。都可以吃吧,听着好像不太好吃,都可以做的很好吃是吧,嗯,行。这是我们说的这个问题哈。然后呢,由这个问题呢出发,大家你看这道题你会不会做。
39:02
啊,这个题呢,我记得还是我上学的时候呢,老师讲过一道题哈。哎,这个组合数学里边呢,有这个题啊,说这个有十级的十阶台阶哈。所以那小朋友呢,每次呢,只能往上走一级台阶,或者是两级台阶。啊,一级台阶或两级台阶,说它一共有多少种不同的走法。哎,看似呢,说感觉像那个排列组合的问题了是吧。嗯,那其实这道问题呢,说下它的本质上就是斐布纳学数列了。你看啊,这个台阶的这个叫阶数吧。这是走法哈啊,有一台阶几种走法。就一种吧,两级台阶呢。两种吧。就是你要么就是一步跨过去是吧,就是一下两级台阶了啊,要么呢,就是走一级再走一级,是不是就两种了,三级台阶呢。有点整不动了,就是吧,其实这三种啊。
40:01
啊,一个一个一个。两个一个一个两个是不是就是三种是四级台阶。嗯,捋一下啊五种啊,你往下走走走走啊,这个也往下,哎走走走走,哎这呢,其实这个关系式呢就出来了啊,这个如果我用FN来表示的话啊。这个呢,你就发现了,它不就等于F这个N。这个。前面两个呢,合了就啊。呃,当然呢,第一个跟第二个呢,你特意的去定义一下,N是一的时候呢,是一,N是二的时候呢是二哈剩下的话呢,就是这样的一个关系式。哎,从第三个开始啊,是这样的关系式。从N。哎,喂。哎,三开始。哎,这儿呢,其实也是一个递归了。你说这个式子,我们怎么去理解它呢?你想想啊,我现在呢想走十级台阶,我说呢,十级台阶就相当于是九级台阶加上八级台阶的个数的和就行了。
41:02
怎么来理解呢?咱先说这个。酒吧。我九级台阶我知道有多少种了,你十级台阶这块你没有选,你只能是一步跨过去。所以说九级有多少种呢,这块呢,其中一部分呢,十级有多少种,其中一部分就是九级台阶的这个种类数是吧。好,然后呢,这个呢,为啥呢,你现在在第八级台阶这块呢。对对,我就直接一步就走,两级台阶就跨过去了。哎,所以呢,把他俩加一起就行,同说诶不对吧,你八级台阶这块我走一步,我再走一步,这不也是一种方式吗。对,你再走一步的话呢,这就归到这个里边了。啊,有点烧脑是吧,哎,这个呢,其实就把他俩一加就是它了。好,这个我们就过了哈,诶这块还有一个小小特点是吧,随着数列的这就数列了不断的增加,诶后一个数跟前一个数的这种比值关系呢,越来越接近于黄金分割点是吧。诶,这样一个小的特点啊,知道就行了,好,那么关于整个递归呢,咱们就告一段落了哈,呃,结论的话呢,大家呃稍微的关注一下啊,就是我们能用循环写的话呢,我们就可以考虑去避开用。
42:08
呃,递归了,但有的时候用递归啊,确实感觉还是比较简单一些的,比如说你像我们讲的那个快排。是吧,你自己一调自己,因为套路一样嘛,诶一调诶就成了是吧,诶你要是能避开的话,避不开,避不开就是人家确实简单,那就该用还用啊就可以了,你知道它性能呢,稍微来讲是差一些的啊。
我来说两句