00:00
函数的递归调用,我们来看一下,那么函数的递归调用在我们函数的调用这个形式里面呢,比较特别。同学们注意,来看一下。那么什么叫做递归调用呢?简单的讲,就是一个函数就一个函数,在函数体内又调用了自身,调用了本身,我们将其称为递归调用,就是函数内部又调用了自己。我举个例子,大家就一下明白了,我们看一个快速入门案例,大家看这面有一个函数叫test。它呢可以接收一个头。如果int in也可以接受一个N,这个N呢,是一个int类型,如果N大于二,然后呢,它就要用自己。传的时候是传一个N减一。诶,大家有没有发现这个test其实就是test本身。再看这个题也是一样,它在这个T的函数里面呢,又调用它自身。好,这个呢,我们称之为递归调用,那同学们来想一想。
01:04
想一想,如果说我们让同学们分析这一段代码执行的,比如说我们这写了一个函数,然后呢,我在主函数里面调用T4,请问这一段代码输出什么?然后呢,分析它的原因。其实这一块就是我们的递归调用的一个原理,那同学们我们来分析一下这段代码会输出什么内容,大家也可以先想一想,如果正在听视频的同学呢,也可以暂停一下视频,你自己先不听老师讲。你自己先分析一下,如果我在这调用调用个TEST4这一段代码会输出什么。明白这个意思吧。那现在呢,我们来分析一把。递归调用。我把这个先注销,我新建一个文件递归调用呢,我取个名叫recu。这个就是递归的意思,那么我就写个DEMO01。
02:04
那现在呢,我们来一起玩一把哈,我们来一起玩一把。首先呢,我们来写一个include。Include std。没有问题,然后呢,写个VO的主函数。对吧,那这里面呢,我们写上刚才这个T的函数,嗯,T的函数它是怎么写的呢?它没有返回值。对,意思就是说如果N大于二,再调用test,然后传的是N减一,我们来玩一把。那写一个test n写上哈。如果N大于二,如果N大于二,那么我们在这里调用test n减去一个一。对。然后呢,我再输出一句话。N。N等于百分号D,为了好看呢,换行。
03:01
然后这里面我们输出这个。因为这块呢,同学们只有一句话,其实可以不扩,如果要扩也行,这样写。同学们看,因为我们前面讲过,如果if这个条件后面的代码呢,只有一行,其实可以不写这个大括号是不是写上也可以,不写也行,那我写上吧。然后呢,我在这里调用一个test等于四啊TEST4现在请问输出什么。大约的数是什么呀?你们先想一想。那这样子我们呢,给各位同学来分析一下这一段代码,它会输出什么来,我先把这段代码呢拿到这边来。拿到我们的Excel。那在这里呢?我们来一起分析代码的输出情况。那同学们这样子,我们还是根据刚才的分析,首先呢,我们有一个计算机的内存。
04:01
这个没有问题,然后呢,仍然是有站这个概念在里边,是不是我在这标起来这是一个站。好,这是个站。同学们看到。在这个站里边呢,我们首先执行的是test是。能理解吧,这是探,也就是说现在上来过后呢,会有一个命战。就是我们叫做主函数站。标记学名叫内战。这个面站里面呢,它调用了是test里面传的是一个四,还记得吧,根据刚原先的分析,一旦调用一个函数,就会产生一个新的站。对吧,好产生一个心站呢,我们来看看这个站呢,是一个太站,这个太站是不是它会接收一个行参叫N,那么在这个站里面呢,就会产生一个N值,注意听讲,现在我问大家这个N是多少。是不是就是四啊,为什么是四,你传进来的不就是四吗?好,这里面就得到一个四注意。
05:07
得到一个式过后,这个代码其实已经到这来了,那么它会行哪一段代码,它会完整的执行一个T的函数,再说一遍,这个站我换一个颜色啊,就是你们看到的这个红黄色,这个站呢,会完整的执行这面代码,那也就是说它下面会去执行一个if。N大于二。大于大于二,然后执行我们的test n减一,各位,这个时候我问大家N大不大于二。N大不大于二,四大于二成立,然后这边是不是就是N减一,那N减一其实说白了就是四减一,四减一不就三吗。但问题来了,因为在这个站里面呢,他又。调用函数,那就意味着又会产生一个新战。在商品。OK,那这个时候是不是这边传进来这个N就变成三了,注意这两个三是站是独立的哦,它相当于说他又去独立的执行这个站,但是大家一定要想象到我们这段代码执行到这儿,下面还有代码没有没有执行,也就是说其实这个地方代码还停在这儿了,等待你返回。
06:15
这个大家一定要分析出来,也就是说你现在是从这个地方。产生的一个战。这个大家能理解不在诶这个表示另另外一个颜色啊,这是,但是下面的代码还没有执行呢,下面还有print语句没有执行明白吧,只是相当于说你在这先产生一个站跳出去了,那这个时候就是N等于三,N3大于二成立,然后这边就是三减一,三减一其实就是。那这个时候他又遇到一个站怎么办呢?还是要严格的遵守我们这个站的调用机制,怎么样又产生一个站?OK,这就是函数递归调用的特点,那也就相当于说在这个地方呢,诶,它又啵的一下又产生一个站,注意在这个地方,它的代码也停留在这,这个站也要完整的执行test函数,只是呢,因为它遇到一个函数的调用,他先开了一个新站。
07:12
那这个占N就是二了,为什么是二?你说传进不是二吗?好,此时此刻,同学们N大于二。还成立吗?也就是说你在最上面这个站,同学们看到这个站。我问同学们问题,这个时候N大于二还成立吗?显然不成立,不成立是不是就应该执行,就不进到if服一句,不进到if服语句是不是就应该执行这个站站里边的就是最上面这个站里边的print语句?这个能理解不?肯定嘛,你按按你这么一个个都执行,大家都是完整的嘛。他把这个地方它补进到一附去,他肯定要自己这个print,那这个print输出的N等于几呢?N等于几看啊,前面它输出N,那我问大家在这个站里面的N等于几,是不是等于二啊,因此各位朋友大家一定要分析出来,此时此刻,此时此刻我们这个地方首先输出的是N等于二,其实是输出上面这个站。
08:14
那么这个站执行完毕,这个print输出完,这上面这个站就执行完毕了,执行完毕过后,是不是根据原先的分析,它要返回来。他要返回,他要不要返回,可要返回,他返回来完了过后是不是这个站里面还有一句话诶。就是这个这个站还有一句话。PRINT1句。PT里面又要输出一个N,那我问大家此时此刻这个N。是哪里面的N呢?是不是他这个本站里面这个N呢,因为这个N肯定是指的他自己的空间嘛,就好像有一个人在一个房间里面叫张三。那肯定是这个房间里面的张三,而不是隔壁班的张三。对不对,说这个N说的就是这个站里面的N,那也就是说这时呢,就应该再输出一句N等于三能理解。
09:07
那同样当他这个地方输出完了过后,是不是他又返回到下一个站。因为执行完了肯定要回来,回来是不是在这个站里面也要去执行他没有执行完的这个print这个语句。此时时刻,这应该数数几啊,同学们。同学们,这个地方应该输出的就是N等于四。当然这边又执行完了过后,是不是他又回到这边来了。回到这儿来了,回到这来,代码test是全部执行完毕,全部执行完毕过后,整个这个程序就退出了,也就是说整个程序结束了。相当于说你可以理解,你可以理解成我们整个这个。程序就结束退出了。当然了,前面呢,我在讲的时候呢,应该这样讲的更清晰,一旦返回是不是这个站就没有了。一旦这个地方这个站返回这个也就没有了。
10:00
一旦这个地方不是他也返回吗,他也返回,这个也就没有了,一旦这个地方执行完完毕,这个也就没有了,当整个站里面连主站都没有了,那么整个这个站就退出,程序就结束,明白这个意思了吧。好,为了保留这个流程呢,我还是把这个图恢复,因为将来同学们还要看嘛,我还是恢复回去好不好?但是大家一定要知道,我们前面讲过一句话,一旦。对,看该当一个函数返回后,该函数对应的这空间也销毁了,只是呢,我为了让同学们将来能够看到这个流程,我就没有把它销毁了。如果我把这个销毁了,你以后就看不到这个东西了,明白这个意思吧。理解这个意思了,那也就是说如果我们这样去用的话呢,应该输出N等于二,N等于三,N等于四,我们来看看答案跟老师分析的是否一样。来,各位朋友,我们来运行一下。我们来一下,走起来。走起来。
11:00
好的,我们运行,我们看这个结果跟老师分析的是否一样呢?应该是完全一样的,如果不出什么问题对不对,诶怎么一闪而过,对我们要get一下。因为我没有把控制台停在这儿,我们执行完毕过后,我们可以看到,诶,你看老师分析的234跟我分析的234完全的一样吻合。好,同学们,通过这个小案例,大家就明白了这个递归的一个特性了,没有非常的重要啊,各位同学,那这样子我看看大家是否真的理解了。如果你真的理解了,我问同学们一个问题,假如说我在这个代码上稍微的修改一点点,我在这个print f里面加了个else语句。有时候改成这个样子了,这边加了个else语句,我问输出什么。能好好想一想吗?同学们,假如说我在这带了一个else。啊,这样子,我们为了让大家看到它的不同的执行过程,我把下面复制一份,然后呢,把上面这个先注销。
12:04
好吧,然后这边呢,我们打个S。也就是说,如果我的代码变成了这样子,请问我还是调用test是会输出什么?跟原原先一样吗?显然不一样,为什么不一样?因为这个地方是衣服,Else,原先是if服一居,那么大家知道if服一居室。呃,如果是if if语句这个地方,不管它进去还是不进去,这句话始终是要执行的。但是如果你改成if else的话,每个站在独立执行T的函数式,它只要进到if语句,那么else就不会进来。是不是这个道理?那如果这样的话呢,我们再来分析这个流程就很清晰了,大家看还是到这来了。到这来呢,最最后最上面这个站,他没有进到这个IF1据,那么那么他就会进到这个A1据,也就是说上面这个二还是输出的。
13:05
没有任何的问题,那么这个做完返回来过后呢,各位是不是在这个地方其实是有一个else这个东西动作。那我问大家A还会执行吗?就是就是这个这个站里面的,这个站里面对应的这个这个else与要执行吗?显然不会执行的,为什么?因为我们讲过if语句是一,一进到IF1句,就不会进到S1句,讲过了没有,因此这个地方就没有任何的输出,下面也没有任何的输,因为你也是进到艺术局了。你进到if就不会进到A这个print语句,是不是,那这个也不会输出,这个显然也没有输出,那也就是说如果我改成else语句,那么最终只会输出一句话,N等于二。能理解什么意思了吧,就是我们只有通过举例才能让大家真正理解什么叫做递归,递归大家一定要非常清晰的知道,每一个独立的函数都会完整的执行它的代码,我把这句话也写进去。
14:08
待会儿呢,我要我要整整理到这儿啊,就是大家一定要特别的注意。我写到这里啊。注意。注意每个函数调用。调用函数时,函数时。这个开辟的,开辟的这个函数站,函数站都会。函数站都会都会完整的完整完整的执行,执行什么呢?这个函数代码。就说你这个站会完整的执行这里面的代码。你这个站也会完整的执行这代码,你上面这个站呢,也会完整的执行这里面代码,明白这个意思吧。好,所以说这句话我都会完成执行函数代码,那这样子的话呢,我们一分析,那么同学们就知道了,那此时此刻只会输出一个N等于二,其他的没有,我们看看是不是跟老师分析的一样走起来。
15:13
走起来,那么一走起来,我们发现呢,的确跟老师分析的一样。只会输出N等于二没问题吧,同学们好,同学们,那这个你理解了过后呢,老师就把这个函数递归的一个机制讲清楚了。一定要认真理解好,现在呢,我总结一下函数调用的规则,其实这个函数调用的规则呢,它本身就是函数啊,函数递归调用的规则和函数调用规则完全是一样的,只是在重复一遍,大家注意听,执行一个函数时,就会创建一个新的受保护的独立空间,你可以认为是一个新的函数站,函数的局部变量是独立的,不会相互影响,这句话怎么理解?看我们这个图,你看你这个站有个恩,你这个站也有N,虽然他们两个的名字都叫恩。
16:02
但是不打架。这上面还有个人呢,但是不打架。就好像我们有两间教室,这有个A教室,这儿有一个B教室,这个A教室有个姓,有个叫张三的小朋友。AB教室呢,也有一个叫张三的小朋友,如果我们在A教室上课的时候,老师说张三,显然这个张三指的是A教室的。如果在B教室上课的老师说张三,显然叫的是B教室的张三,因此他们是相互独立的,虽然长名字都叫人,但是其实是不同的。明白这意思吧。变量的名字相同,但是实际上是完全独立的两个变量。这点一定要非常清晰,好,这个第二点说完了,递归必须向退出递归的条件,毕竟否则就是无限递归,死归了。比如说同学们看,假如我的代码这地方没有写N减一,而是N,各位同学你们会觉得出现什么情况?
17:00
那如果这样的话,他永远都出不来,因为你掉四的时候,你看四大于二进去,进到这里面还是四,四还大于二,它就它就会出现什么呢?它就会出现这个这个站不停的往上走哇一堆。就一堆这个战,那这个就叫战一出,明白意思吧,所以说我们这儿提出一个观点,什么观点呢?就是我们的这个递归条件必须向退出递归条件,毕竟你看我这里写的为什么是N减一啊,因为N减一,N就会逐渐的减小,那总有一个时间它不在大于二。不在大于二,它就不再去递归了,你不相信,你可以试一下,假如我们这写个N,这个地方就会很恐怖了,那一定是个死循环,我们给他跑一下。你看会出现一个什么情况啊。你看运行你看。你看你看直接就停止工作了,是不是啊,不能够这么玩啊,不能这么玩,所以说呢,同学们一定要写,在写代码的时候一定要特别小心,还有一点,当函数执行完毕或者或者return时就会返回遵守,谁调用就将结果返回给谁,是不是讲过这个东西啊。
18:11
就是函数它这个执行完毕呢,本身这样执行完毕是可以,假如你这样写了,他会提前返回,比如说return。那我告诉大家,如果你写这这样的话话的话,那那他就怎样呢?他一旦执行到这里面,他假如执执行到第十句,遇到return,他就直接走了,那下面有如果你这边有代码,他也不会再执行。这个我相信同学们应该能能够理解好不好?就说我们在这个站,就是说白了就是从这个站要退出来,就是老师说的这根线。我们前面讲的是函数执行完毕过后就会。就会退回来,但是还有一种情况,如果在这个执行的过程中,他虽然没有执行完毕,但是他遇到一个return语句呢,它也会提前返回,所以说我们在里面可以再加一句话。
19:03
其实就在这里面可以再再完整的一下,就是当一个函数执行完毕后,或者。这句话待会我们再完善,或者或者执行到return语句。就会返回到调用函数的位置继续执行,就是返回去过后再继续执行,相当于说嗯,它它退出函数,退出一个函数的条件是两种,一种呢,就是我执行完毕了,我正常执行完毕,还有一种就是我执行了一个return了。他也会返回,你比如说呃,你比如说刚才老师说的这这句话。你你假如说老师在这写了个return,那其实这个20呢,它永远都会执行不到。好,注意,假如你这下面还有代码啊,Print什么什么。那就那就执行不到了,明白这个意思吧,好,我相信同学们应该明白,我就不再不再啰嗦了,同学们不再啰嗦了,好,这是我们讲的第四个细节,好,同学们那关于函数调用的一个递归调用的机制,以及它的要遵守的原则,我们就给大家讲解到这里,大家一定要认真体会哈,待会儿呢,我们再做几个练习,加深对递归调用的理解。
20:13
好,这一讲我们就先聊到这里。
我来说两句