00:00
那递归这个东西呢,对于我们来说并不陌生,在学Java基础的时候,老师都应该讲过,我在简单的过一下,呃,递归什么概念呢?所谓递归就是函数或者方法自己调用自己,每次调用时传入不同的变量。递归有助程序者啊,有助于我们编程者解决一些复杂的问题。啊,你看我们今天讲的这个快速排序和归并排序也用到递归了,只要有递归,只要用好了,速度会非常快,今天我们讲这个排序,你会体体现,体现出这个排序确实很厉害啊,比如说我们用排8008000,我们排这个800万个数据。那么如果你用快速排序法,你知道用用多少时间吗?只需两秒。就全部排完。只需两秒,如果你,而且这800万个数据是无序的,如果你800万个数据,同学们,你800万个数据,你用冒泡,你知道会花多少时间吗?
01:03
啊冒啊冒泡。冒泡,你大概要花两个小时都不止我,因为我没有试完。大概要两个小时。这就是。小事啊。两个小时呃左右才能全部排完,这就是区别,那这个它的差别为什么会这么大,因为我们这个快速和冒泡它的机制不一样。今天我们会做一个速度的一个比较好,这个递归确实是,呃,就说我们就提出递归,它有助于我们解决复杂的问题。那为什么递归能解决呢?因为我们在很多复杂问题是它是一个逻辑,就是反复的一个过程。好,递归的概念说到这儿,那下面看递归的一个快速入门啊,递归快速入门同学门呢,在前面已然都学过了,我再简单的回顾一下啊,就是同学们以前如果说专门有学的很明白的,再回顾一下,那么我这里列举两个小案例理解这个递归啊,比如说我们看这段代码。
02:03
比如说我我们来看一个打印问题,再看一个阶层问题,我我就以这段代码给大家把这个递归的一个机制再回顾一下,因为我待会儿呢,要要讲这个递归我回顾一下啊来我们打开一个这个图解,我们把这个递归的机制再回顾回顾。啊,因为同学们休息了一段时间,可能把这都忘的差不多了啊,来,我简单回顾一下,花五分钟回顾一下,那这段代码一旦执行,比如说我在这里有一个主方法。在这个主方法里边,各位同学我就简写了啊,在这个主方法里边,我调用这个test给他传了一个式。传了一个四,那么一旦走这个地方过后,我们这个内存它会怎么跑呢?来各位同学,假如这是我们一块内存。OK,那么假如这是个内存,那你程序肯定是从主方法开始执行的,那这个时候我们可以想象,在我们内存里面就会有一个大的站,注意这是一个整个一个大站。
03:06
OK,这是一个大的站啊,我们简单的画到这里,这个站里边呢,这是这就是个站。这个赞。这是个占占空间,那么占里面呢,它一旦调用一个方法过后,大家必须记住几个原则,它的原则是在我们,在我们这个调用就是递归。递归调用的机调用的这个机制的重要原则,我我把它再整理一下。好。第一个原则就是当我们调用一个方法或者函数时,方法或函数或函数时就会。就会就会开辟就会啊,就会开开一个独立的啊,独立的这个数据空间占空间吧,占空间。
04:00
OK,那么为什么叫独立呢?因为它的数据,它的数据是独立的,好,那比如说我们调用这个主站,那首先这地方马上就会出现一个空间。就在它的这个,呃,系统这个层面就会出现一个主站,这个主站呢,它是独立的主站,是独立的主站里面就调用了一个方法叫TEST4,它一旦调用TEST4呢,它马上又会开辟一个空间,我快速的回顾一下啊同学们。又会开辟一个空间,比如说是这个颜色的,这个叫什么站呢?就叫T的四。哦,他的是这个这个空间这个站。我们可以认为又是一个站,这两个站之间呢是独立的,它怎么保存独立呢?就是我们说的站,它会在跳转的时候,它会保留这个地址。就做做一个现场保护,然后在这边做完了以后他会回来,他怎么知道回到这儿呢?就是因为他会把他这个返回地址先压入站里面。
05:02
啊,这个我们就就不去画它了,到这儿好,一到这个地方过后,我们代码就到这来了。到这来以后呢,这里面这个站里面就会有有一个数据叫N,这个N就是你这传进去的是。好,传奇式,那么它下面执行这个if,依据if n大于二吗?NN大于二,于是它在这里面有个if的执行,这个if里面它执行什么呢?我简单写一下啊,它又去调用一个test,这个时候是N,这个地方的N指的是这个站里面的N,所以说这个问题就相当于是四减一。四减一,那四减一注意这个时候这个N并没有变化啊,同学们注意听你这个四减一这个N本身没有变化,所以说在这个站里面呢,这个N就是四,他一到这儿,他马上发现又调用函数了,根据刚才的调用,呃,递归调用的机制,只要要用方法又要开B站,于是他马上又开了一个站。OK,这个站呢,OK,它也是独立的,我用一个不同的颜色来描述,各位同学好,我比如说我们描述这个颜色,那一旦到到这儿,他又拿到一个N,这个N显然就应该等于三了。
06:13
于是他又去判断这个大不大于二,就是又走这段代码,但是大家知道啊,程序堵在这的。就是你现在这个程序,就是现在这个程序下面代码要不要执行,要取决于将来返回过后怎么走现在,因为它其实在这里又有一个保护的保护地址。返回地址要要存在这它它返回来过后还继续执行下面的代码呢,因为你下面还有可能有代码呀,这点这一点大家要特别的明白啊,我以前学这个递归和二叉树的时候没有搞明白,就是一个机制,这个机制没有没有搞清楚,后面看一些复杂代码的时候,看看不清,看看不明白。因为你这。停这一到这,他其实是从这儿先跳过去了,就你要理解他是从哪走的呢,他到这个地方噌的一下就跳这边来了。
07:05
这点是特别重要的,尤其对我们初学者来说啊,你要诶这个颜色,我还用这个绿绿色吧,它跳出来,同样你你这边地方是怎么过来呢,是到这儿,他到这个站的。好,也要不同的颜色。好,它是这样子的,好同样到这边这个他又判断这个N大不大于二,那显然是大于的了嘛,因为你这个N是不是N,它不是它不是三吗?它大于二吗?它大于二,你又去调用这个方法了,好这个时候就是三减去一个一。同样它这边又有有有一个地址保保护,就是它会把这个地址存下来,然后它又往上继续掉。啊,他又继续往上掉,那我还用这个画一下啊,它又它又跳到上面去了。但是这个占仍然是独立的啊,就是说大家不打架啊,到这呢,这个地方这个N,这个站里面的N1定要理解啊,这个占里面的N就变成二了。
08:03
而且大家看到我们这边的数据,这个N呢,因为是整数,所以它不是因你可以理解成这个数据是独立的,但是如果将来这个各个站注意听,各个站它如果统一用了一个引用类型,那么所有的站都指向同一个空间,这个是特别需要注意的,待会我们那个地图就是各个站通用的,就是为什么你那个排序规,呃,那个规定,或者快速排序快,就是因为它每个站都是操作同一个的空间。这样他就可以做到这么一个效果啊,干干脆比如说啊,我先不画那个啊,不说多了就是假,我的意思就是说,假设我们这个虽然是独立的站,但是也有可能每个站操作的一个空间是一样的,比如说我们这还有个堆。啊,假如说假如说这还有个堆,这这个堆里面呢,咱们有一个数组。哦,宿主。这个把机制理解了啊呃,如果说将来我们每个站在传递的时候,传递是这种引用类型的,那么就有可能这样子的,你这边有一个都指向他。
09:08
好,这个我先暂时说到这啊啊后面我们讲迷宫问题的时候,再再把这个再再说一下,好,那到这来了,到这来过后呢,这个地方又去判断,判断什么呢?A他又去判断这个N大不大于二,显然这个时候不大于了,不大于它就执行下面这句话。也就是说,每个站都会去独立执行这一份test的代码。那这个时候N肯定不大于,它就在这个最上层,它就执行了这个print LN,这个NN,它就打印出这个N等于多少,显然在我们的控制台。假如说我们这儿有个控制台啊。啊,因为因为这个我的空间这有点不够了,我就只能先暂时在这画一下。好,我就挪到上面去了啊,假设这个地方是我们的一个控制台。就是我们的控制台。好,那么这个时候这个控制台,那他就先其实它最最大家一定要理解,它其实执行的是最顶层的这这个代码,那这个时候就输出了N等于几呢?N就等于了这个二,好他把这个二就打出来了,打出来以后这个代码已经到最后了,到了最后了过后呢,这个地址这个站就相当于说结束了,结束它就因为你原先你看啊,你原先掉的时候是从这儿过去的。
10:24
你原先调的时候是从是从这过去的,他把这个代码执行完了过后,他就回来,回哪呢,你从哪开始走的,他就返回到零,它在它这个底层呢,它会有个return,这个return到哪呢?到这个位置来。就这个地址在哪,他就到哪。好,那相当于一伊瑞,那这个站相当于就没有了嘛,你可以理解成你你你可以理解成这个这个站就没有了。哦,没有了,相当于理解成这个,我们你你可以怎么理解呢,你可以理解成整个这儿还有一个,还有一个真正的一个在不停。
11:02
不停给我们找这个占位置的一个占领。就是我们不是原先还有个top吗。啊,他一个top,当你当你每每去搞了一个战过后呢,这个top也在不停的移动。OK,那当然到这地方,他这个执行完了就出战。相当于说出站,那出站就相当于把或或者是把它弹出去,或者是访问不到,因为只要你top往下移动,你就访问不到它了嘛。对吧,所以说你可以理解成这个就没有了,没有的话,他就执行这里面的代码了,那执行代这里面代码呢,它已然已然往下走,它执行这诶它执行到这里,它执行到这里过后呢,呃,执行完了过后,它进入到这个print a n,这个print n呢,它又执行就等于几呢,在这个站里面,这个N等于三。N等于三好执行完这个这个代码里面的这个print过后,这个站又结束了,它又往下走。啊,它走到哪呢?就是还是返回到这个位置,返回到这个位置过后,诶,他又去执行这里面的这个PN,所以说这个N呢,又等于四了。
12:09
好在这里面打出N,等于是好,这个又结束,结束它又往下面走,嗯,这个主函数里面什么都没有就结束,整个就是234这么一个结果,这就是我们这个递归调用的一个基本的机制,这里面他仍是按这个站来玩的,就把我们前面那个站也结合起来了。诶,你看他他还是站的那种特点是先进后出对吧,他也就说大家在学这个递归的时候,一定要有一种,呃一种一种概念,就什么概念呢,他他始终是到了最上层才开始执行,执行完了就往后推,推推再执行。下面代码它是这么一个逻辑,好,那么我们来执行一下这个代码,看看看他跟老师分析的是不是一样就结束了啊。注意每段代码是逻辑是区分的啊,来同学们,我们把这个基本机制讲完过后呢,后面我们讲代码就比较轻松了。
13:04
我始终强调这个原理和机制。就只要你把这个学明白了,至少。看到一些复杂代码,你你不会特别害怕。就是东西不会很难了。好,我们来把刚才的一段代码跑一下,验证一下我们这个执行的流程。因为递归一旦多了,不好验证啊,不好验证,所以说只能看结果。好,我们把它呢,给大家跑一把啊,各位同学跑一把。诶,我这是这么多啊好,我们还在这里,这里,我们这现在讲的是什么呢?讲的是递归,我新建一个包。我新建一个包叫。Because。递归ofsive。好,那现在呢,我刚才有一个最简单的案例,把这个案例呢给大家跑一跑啊IVEDEMO,这是我们第一个小案例,各位同学。
14:03
好的。好,然后呢,我这儿写一个主方法,就是刚才我们写了个主方法。然后这段代码我就不写了,因为它比较简单,我就拿过来用一下啊,各位同学。代码很简单,没有难度。然后呢,我在这儿钓一把。我在这调一把,那就调的时候呢,就test,我给他传一个四进去,好,这边应该输出我们的234执行一下。OK,来,同学们。我们跑一下。我们跑一下。好,我们执行完了过后,我们发现结果跟我们想的一样好,同学们,我们看大家是不是真的理解了啊,我找一个同学说一下这个结果是什么,我加一个S。我加一个S,大家感觉这个结果会怎么样?找一个同学说说这个结果是什么,我加了个S对它有影响吗?OK,找一个朋友啊。
15:01
呃,找一个比较好玩的同学啊,不,不是好玩的,就是比较比较开朗的班班长说一下啊,班班长这个结果是什么?应该一下就答上来了吧。是不是?是怎么样子的,能看出来吗一下。就加S和不加S是不是对他应该是有影响的。哪哪里有印象呢,你感觉。一个都没有吗?N小于二的。是不呃,是不是这个地方,呃,你看啊,这个地方一一段大陆是占领,应该是有的,因为占领他没有进到这里面去。是不是占顶会打一次,其他都不会进去了,因为你因为你这个站这个地方,这个调用这个地方,它已经进到if里面去了,就不会再输出了,应该只输出一个什么。输出一个二就对了,所以说我我写这个东西就是要告诉大家一定要考虑这个每个站它的代码是独立的,所以说如果加个这个else过后呢,其实你们可以看到它输出的结果仅仅是一个二。
16:09
啊,今天大家马上就要反应过来的。就是你们将来这个Spark里面那个算法呀,递归用的也是相当的多,那你如果看不懂的话就麻烦了,好看我加了个else,结果就只输出一个二了。为什么这么说?对吧,你看它就数出一个二,因为这个二大家还能马上就想出来,它是在这个占点,就他啪啪啪找到占点,找到占点的时候,它不是这个N等于二吗?N等于二它不大于二,它不大于二,它才有可能执行这个else语句,但为什么这里面不行了呢?因为这里面它仍然是else的一个逻辑,他已经进到一服了,L就不进去了。他是这么一个逻辑,好同学们,那关于我们这个递归的机制,老师就回顾到这里了啊,我就不再多说,好我们把刚才这个机制给大家,呃。把它整理一下我们的笔记,然后呢就讲应用了,下面咱们就准备讲那段迷宫问题了,好,先把刚才讲的代码做一个简短的回顾。
17:09
和整理。好,各位同学,我向下面,诶这个怎么这么多的代码。往下走一走,哎,这个地方是怎么回事。我要拿一下。好,来把刚才我们讲的这个站的基本介绍和它的一个呃呃,就是机制给大家阐述一下,那刚才我们讲的递归。对,那么讲递归,为了让大家感觉到递归的这个好,它的这个呃价值,我先举了一个应用场景,很经典的一个应用场景,就是迷宫问题啊,这个问题呢。就是这样子的。OK,待会儿呢,我们要解决啊,一会儿我们就要用递归来把这个问题解决了,只要我提出的呢,肯定要把它解决了啊,这个离宫问题,呃,说完了过后呢,我们就把这这个递归。
18:03
把这个递归的一个概念再给大家捋了一把。对吧,什么叫递归呢。递归其实就是这么一个逻辑,就是递归就是函数或者方法自己调用自己,而这种逻辑在我们开发中用的很多。很多啊,就是这样子的啊,它的作用。它的作用是有助于编程者解决复杂的问题。OK,而且呢,确实在很多情况下能提高我们的这个速度,然后我们又讲了一个递归的快速入门。讲了一个递归的快速入门。好地位,快速入门呢,我在这里举了两个小案例啊,一个是打印问题。就是打印那个值,第二个呢,阶层问题我就没讲了,因为阶层我们呃在在学Java的时候已经全部说过了,好,那下面这个代码我们给他跑一下代码。啊,打印就是打印打印问题的代码。
19:03
代码。把代码和这个分析和递归调用,调用调用的机制分析。OK,好老师呢,把这个给大家放到这里啊,我来一个小箭头,那具体来说就这么一段东西,这是我们的代码。这是我们写的一段很简单的代码。那这个代码说完了过后呢,分析示意图啊,上面上面代码的分析示意图。也给大家板述到这里。那这个分析示意图在哪里呢?就是这块也很简单。OK,这是分析示意图。保存。好,那这个递归的一个快速入慢和机制,我们就讲到这里。
我来说两句