00:00
我们已经了解了递归的概念,而且在Java里边同时用循环和递归两种方式实现了阶乘的计算,我们也看到了啊,递归这种实现它确实是非常的强大,它可以非常简洁的把我们想要表达的这个东西实现出来,所以同样是实现一个阶乘的计算,用递归的实现比循环明显,代码就要简洁很多。啊,那这是关于我们之前的这个代码,当然前面没有做测试啊,我们可以在这里边把递归实现的fact同样算一个五阶乘,那结果是不是一致没有问题,是一百二啊,所以这个是递归实现跟循环实现是完全等价的,那同样呢,前面我们是在Java里面做了一个实现SC拉当中同样可以写递归的这样的一个表达,那接下来我们就同样啊,在。下面创建一个scla的object s10,我们现在要测归reccu,没方法写出来,我们还是要计算一个阶乘,直接print left这个函数还是直接叫做fact,那下边我们这里就不用循环再去实现了,就来用递归做一个实现吧,递归实现。
01:19
计算阶乘EF,那里边的参数我们还是把它叫做N,最终返回的程,也是一个int类型,那里边具体的实现呢,跟Java非常的类似,我们甚至可以直接把Java这里的代码直接copy过来,还是N,考虑一个基准的情景,行N等于零的时候,零的阶乘是一直接返回,这个不要自己再调用自身了,然后其他的场景呢,诶,那就是直接。直接去返回当前自身调用N减一的阶乘乘以N就可以了啊,那当然了,这个直接copy过来之后,大家会发现,呃,上面这个RETURN1这里边的这个return其实必须要保留的啊,因为大家知道,如果说我们想要把这个一啊作为一个返回值直接返回的话,在scale代码里边,你必须它是最后一行代码才可以,那这里边后面还有内容呢,所以这个return不能省,而下面的这个return大家看它变灰了,这个是可以省的啊,因为我们要返回的就是前N减一的阶乘再乘以N嘛,哎,所以直接这样用自身就搞定了。
02:32
我们来运行一下,看看得到的是不是还是120。没有问题,结果完全正确啊,所以大家看这个实现跟我们当前用什么语言没有关系。不管是Java还是skyla,都可以实现这样一个递归计算阶乘的一个方,一个函数。那我们也看到了,这个用递归呢,有很多好处,代码可以非常的简洁,而且对于有一些问题而言啊,大家可能会想到它可能就是基于某一个比较简单的场景,然后往前递推一步,得到我们想要的那个结果的,那这个时候呢,如果我们想要直接把它用一个循环表达出来,其实是很困难的,如果用递推的话,那就会非常的简单,所以递递归是一个非常重要的编程技巧,大家一定要掌握。
03:23
那有些同学可能就想到了啊,对于递归来讲,既然是这么重要,那我们在这个编程的过程当中,是不是只使用它就可以了呢?啊,确实是有一些编程语言里边啊,它确实是真的,就是所有的地方都是使用递归的,什么样的编程语言呢?啊,前面我们提到过纯函数式编程语言,比如说像哈斯卡尔纯函数式编程语言里边其实是没有变量的,哎,我们说不是SKY里边能用V尽量用V吗?啊就是纯函数编程语言里边根本就没有变量这一说,因为它要跟数学上的表达完全一样,不可能存在某一个值,一开始等于一,后面又等于二,那所以大家看如果没有变量的话。
04:09
那我们如果要是实现这个for循环,这里边的这个循环变量又怎么控制呢?那这就不能有循环变量了呀,因为本来就不能有变量嘛,所以在纯函数式编程语言,像哈斯卡尔里边,它根本就没有循环的语法,那这里涉及到一个问题,没有循环,那比方说我这里边儿有一段代码,一个打印输出我要执行十次,你怎么样实现这样一个简单的功能呢?在哈斯卡尔里边,它就是完全利用递归去实现这个功能的啊,所以大家看到就是在一个语言里边啊,他如果。直接使用递归实现我们所有的需求,就是关于这个循环的需求都是可以的,直接连循环都可以排除掉,不要诶那大家会想到,既然递归这么好,那是不是我们平常写代码的时候。直接全实现成递归就完事了呢,直接把Java里边的这个循环直接都抛弃掉了呢。
05:05
呃,也不尽然,因为递归还是有它的问题的,前面我们说了,递归可以让代码更加的简洁,这对程序员来讲是更友好了。这就是我们之前说的函数式编程的一个特点啊,它对程序员更加友好,但是之前我们也说过函数式编程。是对程序员更加友好的语言,但是呢,他对于计算机底层执行会更加的难以理解,计算机执行的效率会变低,那同样这里边递归的这种方法呢,也是有同样的问题,它在计算机执行上要耗费额外的资源。它要耗费什么样的资源呢?哎,我们仔细来考察一下的话,就会发现,在递归调用的过程当中,我们在外边比方说我们要计算一个FACT5,那么接下来呢,哎,我们先定义了一个,呃,有这个N作为一个当前的参数啊,是一个局部变量,然后呢,接下来又要调用自身要计算一个FACT4,那大家想一下,我在计算FACT4的时候。
06:09
外边计算FACT5的上下文和它的局部变量啊,当前的这些内容啊,环境可以直接清空,可以直接清除掉了吗?这些是不能清楚的,因为我必须要把FACT4计算完了之后,还要再去乘以N,才能够计算出FACT5的值,然后才能够返回,哎,所以当前我就必须一直等着,之前FACT5的上下文,那些局部变量都必须保存在当前的这个环境里边,哎,所以按照我们之前给大家分析这个JVM内存结构的时候,我们还记得啊,KM站里边。当前每调用一个方法。那么所有的局部变量啊,局部变量表操作数其实都是会保存在一个战争里边的,那当前如果说我们这个保存的时候啊,先调用了这个FACT5,那当然FACT5相关的。
07:09
分量和操作数啊,下文环境里边的一些东西就都要入站,然后呢,他还没有被弹出来,没有被清空,接下来就又要去计算它四。所以我们是在五的基础上啊,FACT5的基础上又进行压战,把FACT4的内容都压进来,那同样计算FACT4还没计算完,我们是不是要又要进一步计算FACT3啊,一层一层在这个占空间里边要做叠加,那我们自然就想到了这个过程,如果说我们现在计算FACT5的阶乘还好啊,最多也就到呃,这个FACT1直接啊,FACT0啊就直接返回了嘛,那如果说我们当前要计算的这个非常这个数字非常大呢,我们递归调用的层级非常的深呢,这个时候就会导致当前的占空间里边要保存的战争会特别特别的多,甚至有可能会直接出现。
08:06
Stack overflow这样的一个异常。战直接溢出了。所以我们会发现啊,尽管递归非常的简单,我们实现起来对于程序员来讲非常的友好,代码非常的简洁。但这是以。耗费更多的占空间资源为代价的,那这里边大家就会想到了,如果要他永远都要耗费这么多资源,耗费我们计算机的性能的话,那在纯函数式编程语言里边,呃,这样的实现它是不是有问题啊?诶能不能对这个东西做一些优化呢?为了解决这个问题,其实在纯函数式编程语言里边啊,或者是像。Scla这样的啊,有函数式编程语言特性的语言里边都往往提供了这样的一个就是优化的方式,那这种方式呢,就是其实非常简单啊,就是我可以把这个递归的函数做一个重新的设计,如果我把它能设计成计算的过程当中啊。
09:14
就是最后一行返回的只有对于自身的一个调用,没有其他额外的计算了。那大家就会想到,如果说没有额外计算的话,那当前是不是就是比方说啊,我们当前就没有乘以N,当然这个计算结果不正确啊,假如没有乘以N的话,直接把计算FACT4的结果就返回了,那大家想我是不是当前FACT5的上下文啊,它的那些局部变量什么都不用保存啊,哎,他自己根本不用存着,只要计算出FACT4最后的结果就是FACT5的结果嘛,哎,所以就相当于我们在这个战争保存的过程当中,就不是一个一个去压战了。而是要计算FACT4的时候呢,就直接把FACT5弹战,然后再把FACT4压进来,或者大家可以理解FACT4的战争就直接覆盖之前的F5的战争了。
10:08
这样的话,那接下来计算F3的时候,就相当于也把它直接覆盖对吧,一次一次只覆盖,那我们这里边的占资源就相当于只耗费一份。这样的话就肯定不会出现战役出了,这种调用方式呢,就是我们对于自身的这种递归调用,永远都放在当前代码块的最后一句,末尾返回的那一句里面。这种调用就叫做伪递归调用啊,所以这种实现就是所谓的伪递归啊,大家要注意,所谓的伪递归,这是说甲的地归那个尾啊,而是尾巴的尾啊,就是尾巴上的递归,所以我们把它叫做尾递归,再来我们看一看,对于这样一个呃计算阶乘的代码而言,怎么样用伪递规进行一个实现,做一个优化呢?哎,我们这里边另外定义一个函数叫做q fact,同样里边我们还是传一个N作为参数进来,返回的是一个int类型的阶乘值,里边要做计算呢,哎,这里边就稍微的要麻烦一点了,因为如果这里直接做这个计算的话,最后不可能就是比方说啊当前的这个FACT5,最后我就直接用FACT4返回,这是肯定不对嘛,那怎么样去处理这样一个呃一个状况呢,那就需要把它再做另外的一层包装。
11:32
啊,就是如果要是说我们可以定义一个内层的函数,这个内层函数是一个是一个伪递归函数的话啊,那接下来我们在外层只要调用一下这个内层函数就可以了啊,比方说我把这个内层函数啊叫做叫做loop吧,就是这相当于实现一个循环啊,它叫做loop,那这个函数如果要是实现之后,我们先把这个写出来,最后呢,我就只要调用一下这个loop,得到结果是我当前要计算的N的接成,那怎么样才能够让这个loop变成一个尾递归的实现呢?
12:11
那我们就不光要传入当前的N,这个N肯定是要传进来的,另外还需要保存一个当前乘积计算出来的结果。就像我们之前在做。在做这个循环实现的过程当中,保定义的这个result一样。然后我们把这个result啊,就是当前的这个,呃,结果作为一个状态不停的。传入作为一个参数不停的传入loop里边来,那它自身每一次调用自身的时候,就可以把状态进行一个更改,那接下来我们就不用再返回再去做重复计算了啊,那所以这里边我们干脆就可以把这个叫做当前的一个result啊,或者说这个可以叫做一个orangent result啊,当然它也是一个int类型,最后这里返回的值,那我们想到了就应该是前后要返回的阶乘值嘛,所以也是一个int具体的实现,我们看一下怎么做呢?这个其实非常简单,既然是要实现一个递归嘛,也得先考虑当前的基准情况,如果N等于零的时候,那这个时候就要直接return return什么呢?
13:27
这里大家需要注意啊,如果要是之前就是零的话,应该return,有同学可能想那肯定RETURN1啊。B要return当前的result,因为我们把之前计算的结果都保存在当前的result里了,所以我们知道return这个current。Arent result,那当然了,另外还有就是。加一般的场景,加一般的场景我们要返回什么呢?返回是调用lo一下,我这里边要调用的当然就是原先是N,现在变成了N减一,另外还有第二个参数,之前是current result,那现在是不是就要把current result在它的基础上就要再乘以当前的N啊?
14:17
哎,所以大家看,这就相当于我们把最后要做计算的这个乘以N放在了它的另外一个参数,保存当前的乘积计算结果上面,这样的话自己就实现了一个所谓的尾递归,我们就相当于把这一呃,这个loop啊,这个递归函数,它的末尾就是一个自身的调用,这样的话,每一次调用的时候,我不需要保存上一层的所有的信息,我的战争里边直接把它覆盖掉就完事了。当然了,外边如果要做调用的时候呢,Loop,那就传的是初始的这个状状态,初始状态N是什么呢?那那那N本来是什么还是什么,对吧?然后那初始的result是什么呢?当然就是一了,就是我们之前这个一开始result给负初值是一吗。
15:07
所以就相当于把用这个伪递归真正意义上的实现了之前呃循环实现的这个功能啊,只不过这里边我们是用是做了一个这个递归实现,这样的话,在真正执行的过程当中,我们对于占空间的耗费也也就不会那么大了,每一次我们只是把战争做了一个覆盖。啊啊,那所以这里边大家需要注意,就是在skyla里边,如果我们已经实现了这样一个伪递归,大家其实会发现idea里边这个提示是不一样的。你看上面这个如果是一般的一个递归的话,它有点就像一个这个绕圈圈的一个蚊香一样啊,就不停的绕,不停的绕啊,这就把我们绕晕了,对吧?呃,就当前它的这个效效率是不够高的,有可能出现这个占占空间的一出,而如果要是大家真正实现了纬递归的话,它这里边就是只绕一圈就可以了,就不停的覆盖之前的纸啊,那当然对于这个SC而言,其实是还有一个特别的注解的,就是比方说我们要实现这个loop的时候呢,我们可以在前面按一个at pass go rap sc里边的annoation啊,一个注解,把这个加进来之后呢,诶,那就可以确保我们写出的这个代码必须是一个正确的伪递堆程序。
16:26
如果你写出来的不是一个正确的委地规,你加上这个注解之后,它就直接报错了啊,就像前面这个,你如果要是在这儿啊,我们直接加一个at,有rap的话,大家看这里边就直接报错啊,所以有了这个注解,在写的时候就能保证自己不出问题,那这里边大家需要注意,就是在SC拉里边,那那有同学可能会想,那Java里边是不是也可以直接写这样一个伪递归去做这样的一个优化呢?呃,我们可以写成伪递规的形式,但是在Java里边这个是无效的,因为伪递归的优化是依赖于编译器的,编译器要知道我们当前遇到这个委地归的时候,我是把那个战争直接做覆盖,不要做啊,进一步的那个战的这个叠加,对吧,继续压战的这种操作,必须得编译器知道这个操作我们才能够优化出来啊,所以这里边不同的语言对于伪递归的支持是不一样的,只要是真正的函数式编程语言,它都是会支持伪递归的,所以在SKY拉里边,大家有时候会需要注意一下啊,我们把它写成伪递归的形式,那最后我们还是来测试一下,看一看不是一样的FACT5。
17:39
算的结果对不对?没有问题,H120啊,这就是关于递归和尾递归优化这一部分内容。
我来说两句