00:00
这一节我们来学习相关算法储备啊,递归深入。递归啊,咱们在基础的JS学习当中呢,肯定是学习过的啊,比如非常经典的费波纳切数列,嗯,费波纳切数列呢,它就要用递归来去实现,我们来看一下这个数列,这个数列的规律呢,就是后边一项等于前边两项的和二等于一加一,三等于一加二,五呢等于二加三,八等于三加53等于五加八啊是这样子的。然后现在他让你用这个递归的思想输出斐波纳契数列的前十项,啊,那么这就是一个经典的斐波纳切数列,那么我们现在就可以设一个函数,比如说叫fe,那么fib函数N呢,它就能输出DN项啊,就下标为N这项的呃值。比如说现在我问你肺四等于几啊,就是肺四,肺四就是01234,他就问你肺波纳切数列中第四项啊,下标为四的这项就是第五项下标为四这项,那么很明显FE4它是不是就等于Fi吧,三加FI2啊,那不就是Fi n减一去加上一个fe吧,一个N减二吗?
01:14
对吧?哎,那现在就形成了递归啊,就相当于是啊,前一项加上前两项啊,那前一项不就就等于它的前一项加前两项嘛,啊咱们来看这图就FEB4是等于三加二了啊,第三项加第二项下标为三这项呢,又等于下标为二这项加下标为一这项啊,然后下标为二这项就等于下标为一这项加下标为零这项啊,但是我们这个递归一定要有终点,就是这个递归一定是要能结束的。它不能无穷无止的递归下去,那所以说这个递归呢,要想能结束的话,那我就必须要告诉咱们的这个程序,就是WEB1和WEB0前两项。啊,大家看一下前两项是不是都是一呀。所以说这两个常数一旦确定啊,那么这个时候呢,下标为一的项,下标为零的项都是一,那这个时候下标为二的项呢,哎,它是不是就能确定就为二对吧,一加一到二啊。
02:09
哎,然后呢,下标为二的项啊,这是下标为一的项啊,二加一这个都是三对吧?哎,然后这个又是下标为二的项,那你还要算一下,一加一等于二,三加二呢,这就等于五,所以就把FI4就算出来了啊,就是当它呃一层一层展开之后,然后到最底下的时候,哎,到这种FI1和FA0的时候,它就能够去返回啊,他就会返回上一层就去,呃,他就能把当前这层的结果返回上一层,那么这个非博那技数列的话,咱们不是零基础课程啊,咱们不是零基础课程老师讲的比较快,这肯定是咱们在嗯,就是学习JS的初期,老师就演示过的,好,我们现在把这个题呢,我们写一下。好,我们创建一个网页啊,这个就叫递归深入。递归深入一啊,好,我们来看一下这个费波纳契数列啊,我们把这个题目抄一下,当然这个题目还有后半句,它是让你思考代码中是否有大量重复计算,这个我们一会儿思考。
03:12
对吧,我们先把这题输一下啊,那我们现在就创建一个函数,哎,创建一个函数函数啊,这个函数的功能啊,是返回下标为N的这项的数字。啊就行了,所以说这个咱们这个函数呢,就叫做fib接受嗯,下标N,那么Fi n呢,它就会返回Fi n减一是不是加上一个费吧,N减二啊。好,那这样的话你就会发现,如果我要去算FI6,那它就会返回FI5加FI4,哎,那FI5呢又是FI4加FI3 fi4呢又是FI3加FI2,那这样的话你就会发现啊,他到最后永远结束不了,为什么呢?因为到FI1之后,他还会算FI0加Fi负一呀。
04:00
哎,所以这个时候咱们就对他就需要咱们去进行一个if语句的判断啊,判断这个N是不是零,或者N是不是一。啊,然后如果是D0D1的话,就直接返回常数一,否则的话啊,就返回它这个else不用写,事实上这个if语句也不用写。啊,因为这块可以直接写成三元运算符,就是看你这个项是不是零,是不是一呀,如果是的话,我就返回一,如果不是的话就递归对吧?哎,那你就看你这个下标N。下标N啊,是不是零或者是不是一,如果是就返回常数一,哎,如果不是就返回啊,就递归,哎,他这就递归了。啊,所以他这是这样的一个情况,那么这样的话呢,我们就可以看一下输出conso dialog fe6下标为六的这项的这个数字是多少。好,我们现在呢,可以去运行一下它,我们把它给。
05:04
哎,用live server,我们给他跑一下,打开控制台,我们可以来看一下啊。好,它输出的是13。啊,那也就是说下标为零,123456,下标为六,这项呢,它的值是13是没有问题的啊,那前十项我是不是就可以用循环语句来进行输出,好,那我这个时候就可以用循环语句来进行输出了,Let I等于零,I小于等于,呃,前十项那就小于等于九是吧,I加加,然后我就可以输出fe Di项,这样的话我们这个数列就出来了,11235 83 21 34 55。啊,这是没有问题的啊,好了,所以这个呢,就是一个非常经典的一个递归的这样的一个写法,那么这里呢,需要给大家强调的就是一定注意这个递归呢,它不能无休无止的递归下去啊,它一定一定要有一个结束的终点,就是呃,当N等于等于零或N等于等于一的时候,这个时候呢就不要递归了啊,它这个时候呢,就需要直接返回常数一。
06:06
这个非常关键。因为只有你能有递归的一个底线,就是它的一个终点,那这个时候呢,它才能往回一层一层的回溯,对吧,它不能再这个一再分叉,再往下分叉,再往下分叉,那不就是。子子孙孙无穷匮也嘛,那不就死循环了吗?对吧?所以这个呢,就是非波纳妾数列的一个最基本的写法,那这个时候我们就要来研究一下这个东西啊,就是说他是说请你思考代码中是否有大量重复的计算。啊,应该如何解决重复计算的问题,其实是有的,为什么是有的呢?咱们现在可以发现,你算FI4的时候呢,就要算FI3和二,而算FI3的时候呢,也要算FI2和一,也就是说FI2你看在这里我们眼睁睁的看见了,它被计算了两次,它被计算了两次就是我FI4它会FI3 fi2就分两个分支嘛,那么FI3它就会展开两个分支算FI2而。
07:03
你这个分值也算了,次语r fe2啊,所以这个时候你就可以去输出对吧?哎,输出我们可以看一下测试一下啊,就是说现在进入了VB函数。好,我们把这个N给。嗯,输出这个时候你就会发现,你看啊,他一上来,诶,这个递归次数特别多,我们不是算了十吗。对吧,他算了啊,这是一开始是零,哎,然后1210啊,你为什么是一开始是零,因为light I等于零啊对吧,那你可以发现,比如说FE82被算了多少回,这是一次,这是一次对吧?然后这是一次,这是一次。那FI2被放了很多回,FI3呢,也被算了很多回,这是一次,这是一次,这是你看太多了。最恐怖的是,你只要算了F3 fi3就会展开成这么好几只。明白吗?所以说它带来的计算量是非常大的啊,那再给大家重新拿这条数列讲一遍就明白了,就是比如说我现在要算这个数字是几。
08:05
那算这个数字是几,我是不是就要知道前两个数字是几,但是前两个数字你已经在之前算过了。你明白吗?就是这两项我已经在,呃,就是在前面的计算算过了,就我刚才不是已经算过这一项是几了吗?那我这时候在算这个这一项是几的时候,就不用再算前面这两项是几了,他应该能得到答案。对吧,我不用说立刻当场去算前一项加前两项,因为这个时候我可以看看前两项是不是算过了。啊,所以就不要再造成大量重复的计算,你看这里FI3FI8。对吧?哎,那这里FI3又展开二和一,它又算了一次FI2,而你FI2的时候呢,这一次再用FI2的时候,它是不是就。没有记住曾经算过P82的值。那怎么解决这个事情啊,那这个时候呢,他其实就会有一个cash思想啊cash cash这个单词呢,老师已经给大家查好了,它就叫做呃缓冲啊,缓冲存储器,实际上就是咱们呃大家最爱说的两个字缓存,什么叫缓存呢?就是我现在可以用一个对象,这个对象我用自然数来当做键。
09:17
啊,那有的同学说老师能不能用数组,可以用数组,但是用数组的话吧,呃,一会我们说用数组,他就不用递归了,一会我们再讲一个不不递归的方法,算斐布拉契数列,你先跟着邵老,呃,跟着邵老师的思路走,就是我们一开始比如说零进来的时候,I等于零的时候进来了,那I等于零的时候,我是不是就可以缓存记录住I等于零的时候,这一项是一样。对吧,缓存记录一下。对吧,诶,然后这一项也是一,然后下标为二的这项我缓存啊,我缓存下标是。对吧,值是二,然后下标为三的这一项,它是三。啊,然后下标为四的这项它是五。
10:00
诶,我记录下来,下边为五,这项呢,值是八。对吧,哎,然后我就是我每遍利一个数字,我就给它缓存一个数字,那这样的话,当我再去问比如说菲波斯得几的时候,我先看看我缓存对象中。有没有,如果缓存对象中有,那这个时候我是不是就可以直接读取他的值,如果没有的话,那我这时候再去算,然后再把算出来的这个值呢,是不是加入到缓存对象当中。对吧,哎,是这样的一个思想啊,咱们再说一遍,很简单,它是分为两步啊,第一步就是我去,比如说现在循环语句到I等于四了,那这个时候呢,就势必要去算FIB3。对吧,哎,加上一个Fi几啊对,加上一个FI2,那这个时候不要先着急算FI3啊,因为我们先去看看缓存对象中有没有三这个数,如果有的话直接拿来用,哎,然后FE82也是,如果有的话就直接拿来用。对吧,哎,这没有问题。啊,直接直接拿了用,那这个时候我们就可以算出下标为四的这项,它实际上答案是五,那这个时候再把这个四这一项是不是就存进去,把这个五写进去,那一会儿你再算FI5的时候。
11:09
它是不是就等于FI4诶加上FI3,那你有没有发现FI4加上FI3就很简单了,因为下标为四这项已经在缓存中刚才写入了。所以这种缓存思想实际上是在view的底层啊,包括这个抽象语法树的建立,也包括咱们的虚拟节点当中啊,都都会有这样的一种思想,实际上咱们在之前的这个虚拟节点和这个地步算法那个课程当中,是借助过这个缓存对象的啊,但是当时呢,我们没有把这个算法储备,单独的去讲解,单独的摘出来,单独的拎出来。啊,所以就有同学呢,就说建议老师,就说老师,我们还是想单独的看一看这思想。对吧,那所以说这个用缓存来结束的话,那我们现在就可以去做做这件事情啊,用缓存来做的话,那这个就是呃,做这件事情,比如说我们现在就可以做一个叫缓存对象。
12:01
啊,那这个对象呢,我们就可以叫,呃,比如说这个对象的名字就叫做cash。啊,Catch,好,它是一个空对象。就行了,那现在的话,我们是不是就可以首先先去判断咱们的缓存对象中。有没有这个值。对吧,哎,如果有就直接用啊,所以咱们可以判断一下,就是看咱们这个cash中是不是has own property。诶,是不是有啊,是不是有这个N这项的属性啊就完事了,当然这个判断也可以用n in啊,这个cash啊这样的去写,也可以用这个,呃,In运算符,In运算符和has own property啊,它有一点点区别在于什么继承啊,原形链的时候它有一些区别,但是现在呢,这些区别,嗯,没没有没有继成对吧,所以它区别不大啊,就是如果n in开始啊,当然也可以用这个has on property都行。啊,那咱们就用has on property吧,如果他有对,那我是不是就直接返回咱们的cash对象中的?
13:04
这个值啊,你注意这里不能点N啊,千万不要点N,因为N这个东西它现在是一个自然数。啊,你比如说是开点点三哈,开点四它。它现在要表达是这个自然数这个项,而不是N属性,你点N表示我要访问N属性,我这里是不是没有N这个属性了,所以它就会返回安find啊,一定记住,当我们要用变量,当我们要用变量来当做对象的键名的时候,这是变量啊。对吧?当我们要用变量来当做对象的键名的时候,那这个时候我们是不是就应该怎么办?对,是不是就应该用方括号啊,那就访问这个N所代表的这个数字的这个在开始这个对象当中的那个值就行了啊,这样好,Else不用写,因为这是函数,函数遇见return就会返回吗?所以不用写L,那底下就表示的是返回啊,缓存对象是不是没有这个值啊。
14:02
啊,那缓存对象没有这个值的话很简单,那我现在就要两步第一步。对,我需要把它缓存对象写进去啊,先算出来对吧,算出来啊,计算出来。哎,计算出来那就let一个V或者Y啊,Y一个这个V,哎,我们给它算出来,那就要看N是不是得零,N是不是得一,如果是就一,如果不行的话就返回,看见没有,哎,然后这个时候呢,我们是不是还要写入缓存啊,写入缓存那就是cash的N这一项就等于V。哎,然后还要返回这一项的值啊,你不返回的话,你你以后递归不就要不到这个值了吗。对吧,哎,是这样子的,那这样的话你就会发现,诶,我们的这个啊,计算就会非常快,为什么计算非常快呢?因为总的递归次数减少了啊总的递归次数减少了,能明白吗?诶计算量减少了,你不信的话,我们可以直接在这个里头,我们可以输出一下conso Di log,对吧?诶命中缓存啊,命中缓存不用计算了,哎,直接。
15:04
呃,直接用递归的次数减少了,因为它直接从缓存中得值之后呢,它就不会引发新的分支了,咱们可以看一下,你看命中了很多次。对吧?哎,第一次进入fe函数算个零,然后算fe函数一,那这个时候你就会发现FE1已经被加入缓存了,所以这个一就已经命中了,再来就已经命中了,那这样的话你可以看一下总的递归次数啊,咱们可以统计一下,咱们现在就啊cons对吧?哎,第二,呃,这个统计就是康点count对吧?哎,计数。啊,计数一下,好,我们来看一下,那这个时候你就会发现这个,呃,计数是26,到最后咱们这个fe呢是26,这个55不是啊,这个55不是计数,这个55是最后这个斐波纳切数列的那个,呃,数列的第55项不是数列的第九项下标为九的这项,他不是55吗。
16:00
哎,就是这一项啊,55,所以这个55不要看错,是F函数一共触发了26次。发现了吗?就是fib函数一共只被触发26次啊,Fib函数一共只被触发了26次。好,那如果说我们,呃,现在把这个if已经删了,恢复成刚才的状态,也不写入缓存了啊,也不存变量V了,直接返回对吧,直接返回刚才这状态啊,那咱们这回看看基数,看见没有计数是不是276次啊。有没有发现计数是276次啊,那为什么他一下子从276次就变成了20多次了呢?为什么呀?对,这是因为它不重复计算了啊,就是你你你比如说要算这一项的值,那这一项不就等于前两项相加吗?对吧?那如果说你没有缓存,那他就开始算这前两项分别是几了,而算它呢,又要算他俩,算它呢又要算他俩,算它呢又要他算他俩,所以说你曾经算过的东西呢,又被大量重复计算了。所以这个时候呢,我们就可以用这个缓存对象啊,那这个缓存对象你现在就会发现,它是随着你啊,就是算的东西越来越多,它呢也就会越来越饱满。
17:10
对吧,哎,那到最后我们可以来看一下。Cano Di log on,我们这个缓存对象。啊,刷新,你看这个缓存对象在这我们也可以把它放到循环语句当中,我们看一下就是随着你的计算过程。哎,你看你的缓存对象是不是阵营在越来越大呀,啊,你看。这里边儿的这个成员也会越来越多。哎,都被缓存起来了。啊,非常的好用啊,所以它呢,实际上就是一个非常好用的这样的一个呃,缓存的一个策略,那这个东西大家不不要以为啊,对吧?哎,不要以为这个东西不是特别的关键啊,就是呃。大家可能会认为说说这个算法思想能提高效率啊,但实际上在VI的底层,包括咱们的上上次咱们那个啊免费课程就是讲这个递步算法的时候,实际上里面呢,也是有一些缓存对象啊,来看它是否命中的,哎,这样的话可以极大的提高这个效率,尤其是在递归的时候啊,咱们大家一定要注意要去使用这个缓存。
18:16
好了,那么有的同学就说,老师,那实际上这道题可以不用递归来实现啊,就是可以直接去写一个数组一一,然后呢,我们现在呢,就是书写一个循环语句,当这个数组的lengths小于等于十的时候,对吧?哎,我就让这个数组push这个数组的下标。最后一项啊叫Les减一加上这个数组对吧?哎,Arr的Les减二啊这样写,那这样的话,循环结束之后呢,我们这个时候再输出这个数组。啊,Console dial log这个数组,那这个时候的话是不是就呃也能把非奔纳线数列生成的是对的,这个答案是对的,但是这里没有利用递归啊,这里没有利用递归,所以面试的时候,人家面试题上会明确的书写,就是请用递归实现费莫纳切数列啊,同学们是不能写这种方法的。
19:10
啊,就不能直接借助一个数组啊,当然这种方法很巧妙,因为这个数组本身就是缓存呀,对吧,你把二给写进去了,然后呢,这个时候他就算后两项是三对吧,它自带缓存,你发没发现自己就是写进去的一瞬间就存进去了,很巧妙,但是呢,它不是递归,发没发现这没递归呀,他甚至连都没有创建函数,没有创建函数,那它肯定不是递归呀。对吧?哎,所以大家一定要记住啊,就要用这种方法啊,就要用这种方法来去标准的实现这个斐波纳器数列啊,缓存对象一开始是空,然后每算一个值啊,就要把这个值写入缓存啊,咱们把它写上,也就是说,也就是说。哎,每算一个值,就要把这个值。是不是存入对象啊,对吧,哎,存入缓存对象啊,这样子的啊,每算一个值。
20:06
好,那么这个练习呢,希望大家能够认认真真的啊,书写几遍。
我来说两句