00:00
同学们,我们接着递归,继续为大家讲解。那么现在我们来看递归这一个知识点,它可以解决什么样的问题呢?大家看,我这里罗列了一些这样的问题。比如说各种数学问题。比如说后面我们要讲的八皇后,汉诺塔,刚才讲的阶层,还有刚才提的迷宫,还有求和男子这样的问题呢,都可以用递归来解决。这里呢,我有点资料给大家分享一下,叫谷歌编程带话,嗯,编程大赛,我们来看一下这里面的这这些有哪些题好,同学们可以想的一些题,同学们看,在我给他分享资料里面呢,有一个谷歌算法大赛,其中里面有这样一些问题,像磁盘公交车矩阵中查找单词路径数。求和难字扔石头,我们就找一个题来看啊,看你会,你遇到这个问题会怎么解决,求和难字呢,它是这样的一个要求,同学们看这里。
01:04
他说,呃,你有几个相同的球,球的数量给你了,然后呢,希望把这些球放在几个篮子里边去,每个篮子呢,都有相同的容量。用这个basket表示男子的个数,然后用capacity capacity呢表示表示什么呀?表示呃,每个篮子的最大容量就是每个篮子能够装几个球,然后用bos bos表示球的数量,这个basket baskets表示篮子的数量,这个表示容量,这个表示球的数量问。问,为什么呢?表示归类到篮子里的球的数量。球的数量,也就是说返回之是什么呢?把球归类到篮子里的方式的数量,换言之,说的再明白一点,就是说。问,也当我把这几个词给你过后呢?问有几种方法?
02:03
问,有几种方法,比如说他这举举了几个例子,比如说把两个球放到两个篮子里面,你有几种方式呢?021121。看到没有就说他他是这个意思,就是说白了就是一,就是什么呢?就是把我们这个球可以放到篮子里的数量的,呃。把把球放到篮子里面的方式的数量有哪些,并且把这些方式给罗列出来,这就是一个经典的需要使用递归来进行。处理的一个案例,那除了这个题之外呢,还有刚才我们说的其他题,比如说扔石头,扑克牌,呃,扑克牌这些问题都可以用递归来解决。那除此之外呢,还有哪些也需要用到递归呢?比如说我们后面用到这个排序算法,像快排、归并排序、二分二分查找分制算法都会用到递归。
03:00
递归呢,它还可以将占解决的问题用递归。来解决,那么这样的代码就看起来比较简洁,所以说递归能解决的问题还是非常多的,包括我们后面我们学的这个数。图求求这个最短路径,还有最小生成数都会用到递归。那呃,这是他能解决问题,那么我们再来看看递归,他在我们使用递归的时候需要遵循的有哪些重要的规则,给大家聊两句。如果你不遵守这个规则呢,那么这个递归一定会出问题。刚才我们是不是把递归的。这个机制给大家回顾了,现在我们看看递归在使用的时候需要注意什么事项。那第一个。当执行一个方法的时候,就会创建一个新的受保护的独立空间,我们把这个称作为占空间,也就说递归,其实它是它这个底层呢,还是用到占了,只是我们不知道而已,那这这句话怎么理解呢?这句话其实就是刚才老师讲的这句话。
04:03
就是说当我们呃程序执行到呃一个方法的时候,它就会产生一个独立的空间,这个空间呢,你可以认为是一个占空间。占空间它是独立的啊,好像把我们每一个空间放在一个大的站里面去用完了,那每次用,每次执行的时候呢,是把新的站压在这个站点。当然执行也是从我们呃最上面开始执行的,执行完了再回到下一个站,执行完了再回到下一个,再执行完最后回到这个站底的这一个命战的时候呢,整个程序结束。所以你看递归它这个底层呢,编译器的底层其实用到了这样的机制能理解,所以说我在这儿说的是这样一句话,第二句话,方法中的变量就是每一个占空间的。局部变量是独立的,不会。相互影响,比如说刚才我们在每个站里面产生这个N。
05:00
就是局部变量,他们相互不影响,明白这意思吧,所以比如前面讲的啊,比如。比如那个N值N这个变量。变量。那么有问有,有些同学就问了,说老师,那我们在递归的时候,有没有一种可能性,每一个站它共享的是一份同一份数据空间呢,是有可能的,有一点啊,如果。说如果方法中,方法中使用的使用的是什么呢?是这个引用类型的变量,引用类型变量。那就会干什么呢?就会就会共享该。共享共享。该引用类型。共享该引用类型的数据。这个大家能理解吗?就说如如果我们方法中使用使用到的是引用类型的这种变量,就会共享该引用类型的数据。打个比方,后面我们讲这个迷宫问题的时候,就会遇到这个问题,我们传的是一个数组。
06:05
比如说你,你在传的时候不是基本数据类型,而是一个数组,比如数组。比如数组你看啊,嗯,你什么意思呢?就是说将来也有一种可能性,就是我在这一方传调用这个test的时候,传的不是一个基本数据类型,而是一个引用类型,是个数组,那么也有可能是出现这样一个情况,比如说我在我我这个地方有一个引用类型。有一个引用类型。对吧,也可能是个对象放在这儿了。放在这儿的,那么每一个就是我这个空间用的是。这个数据。再比如说这个这个站里面呢,用的也是这份数据。好,我把这个颜色标标一下啊,标成这个绿色的。这个呢也标成绿色的,当然在这个站呢,也有可能用的是这份空间。
07:00
明白吧,就说也有可能我们产生了很多很多的独立的站,但是这个站呢,每个站他们用的这个数据却是指向的同一份儿数据空间。这是有,这也是有可能的,比如说我们传的是引用类型。我们传的是引用类型,好,那关于这个这点呢,大家要灵活的去理解,灵活的去理解,后面呢,我们讲这个迷宫问题的时候,就会是让多个站。共享同一份这个数组。好,第四一点,地归必须向退出地归的条件,毕竟否则就是无限地归,就是死归了啊,死了,死在里面出不来了。那这个怎么理解呢?还是以这个案例来说话,你看大家有没有发现我在调这个打印问题的时候,我是N减一,但是我为什么没写N减一呢?因为如果你写的N加一,大家想一想,你这个N会越来越大,就是你每次传进去的这个值呢会越来越大,那么你本身传进去的时候,这个就已经是四了,四再加一变五。
08:08
变五的话,那就意味着我们永远满足N大于二,那就不停的往下归,归,它会出现出现什么情况呢?就会出现一个。一个战战战役出的问题,我们可以演示一下看啊,我先把这个去掉。现在呢,我故意在这写的是N加一来,我还是执行,你们看效果。同镜看。马上就出现这一个可怕的错误了。这个错误叫做stuck overflow error就是站溢出。战一出就说我,我在这儿提的意思就是说,我们在写递归的时候,你一定要注意这个递归,他一定是向退出递归的条件逼近。否则就是无限地贵。无线定位就就会出现什么呢,就会出现刚才说的。出现刚才所说站over overflow。
09:03
而overflow这个L。而且大家看到这是个error。Stuck overflow,也就是刚才同学们看到的。这个问题。好,那所以说你看这个地方呢,我们还把它改回去啊,不然的话,你这肯定就没有意义了,好,这个说完了之后,我们再看第五个,当一个方法执行完毕后。就是在递归的时候,方法执行完毕,或者遇到return呢,就会返回遵守,谁调用就将结果返回给谁,当时当时,同时啊,同时当方法执行完毕或返回时,该方法也就执行完毕了,这句话怎么理解呢?还是以这个图为例,比如说。当我们最上面这个绿色的站执行完毕了。它就相当于返回到。调用这个test的方法的位置,如果有结果就把结果带回来,如果没有结果呢,相当于在这个调用的位置继续往下执行。再说一遍啊。
10:00
就是说如果一个站。代码执行完毕了,或者遇到了一个return语句,那么这个呢,就会返回到哪里呢?返回到调用的这个位置。如果呃有返回有结果,就把这个结果带带回来,比如你返回的是有个具体的值,它就返回来,如果没有结果呢,就返回到这个位置,继续往下执行,注意啊,听那句话,继续往下执行。你不能说我返回来过后,我就下面的该输出的语句,或者该怎么样就不执行了,不一样的,它相当于说继续往下走。OK,好,同学们,那关于递归要遵守的这么几个规则呢,老师就先给大家介绍到这里,好,刚才我们讲的是什么呢?简单整一下,我们刚才给同学们说一下递归能够解决什么样的问题。他能解决的问题其实挺多的,就是因为在实际的开发中有很多问题他都是一个重复的一个思路,比如说汉洛塔对不对,再比如八王后,再比如说我们的这个排序快排规定,其实都用到递归,因为很多问题都是一个重复的过程。
11:09
所以只要是重复的,那么都有可能用到递归,好递归能解决问题,我这整理一下啊,整理了大概有这么,呃,总总结了这么几点。当然,呃,在工作中还遇到什么问题,大家灵活的对待。第二个呢,我给大家说明了,我们递归它的遵守的重要的规则有五个,这五个规则呢,你要不遵守就有可能出现。递归,出现一个无限无限递归,或者是本身就错的,OK,他遵守的规则呢,我这里整整理了有五个。啊,有五个,哪五个呢,这写到这来就行了。尤其要注意哪哪一点啊,就是这一点。他必须向退出帝国的条件逼近。不然就死灰,就会出现stuck over overflow。还有一点就是返回,当我们这个方法执行完了,他怎么返回是遵守,谁调用就将结果返回给谁。
12:08
那如果没有结果怎么办呢?没有结果他也要返回啊,没有结果然后继续往下执行。继续往下执行。好的,那关于刚才我们讲的递归能够解决的问题和递归需要遵守的规则,先给同学们介绍到这里,待会儿呢,我们就要开始写代码了,当我们拥有了递归这样一些基本常识过后呢,我们就用代码来完成这个迷宫回溯或者迷宫问题,好吧,好,同学们,关于这点我们先说到这里。
我来说两句