00:00
接下来我们要介绍的是函数式编程里边另外一个非常重要的概念,那这个也可以说是所有编程语言里边比较通用的一种编程技巧了啊,那大家应该也听说过,这就是所谓的递归,什么叫做递归呢?简单来讲就是一个函数或者方法在它自身的内部又调用了自己,那这个时候我们就把这种调用叫做递归调用。那自身调用了自身的这种函数,我们就叫做递归函数,所以从字面上来理解的话,什么叫递归呢?那就是依次的规约到自身上,就不停的自己调用自己,这就是所谓的递归。那这里大家可能会发现一个问题,就是假如我们要是在一个函数里边不停的调用自己的话,这不就循环往复,我们永远都出不去了吗?哎,那怎么样能解决这样一个最终退出的一个问题呢?那这里边大家就需要注意啊,在一个真正能够执行的递归函数里边,我们一定要有一个跳出的逻辑啊,就是你总得有一个镜头,你不能无限的调用自身,所以大家要注意啊,就是我们可能要有一个条件判断在某种条件下。
01:15
我们的这个递归函数就不需要调用自身了,然后直接返回一个值就完事了,这就是我们所说的基准的条件,基准的情形就是我们递归跳出自身调用的这种逻辑,那另外还有就是说为了用递归去解决一些问题的时候,设计算法的时候呢,那就往往是递归调用的这个参数要有一定的规律。啊,那这个可能说起来比较抽象啊,那接下来我们举一个具体的例子,这个例子可能大家也见过,就是计算阶层,那阶层呢,在数学上我们都知道,如果要表达的话,比方说我计算五的阶乘,数学上是五后边加一个感叹号来表示,那什么叫做五的阶乘呢?就是。
02:02
连乘啊,就是12345自然数啊,一直乘到五,得到的结果就是五的阶乘,当然这个数也非常好算啊,二五一十三,42,当然得到的就是120了,这就是阶乘的一个定义,那如果说我们想要写一个代码来直接把这个阶乘写成一个函数,或者写成一个方法啊,我们是传入当前要计算谁的阶乘传一个N进来,然后呢?哎,当前代码就直接能把这个N的阶乘计算出来,返回结果应该怎么样写这个代码呢?这其实有两种思路,一种大家可能比较容易想到,呃,我们直接用一个循环不就搞定了吗?比方说你要计算N的阶乘,那我就写一个for循环,然后就定义一个循环变量,从一一直到N啊,我们这里不是计算N嘛,那就一直到N,然后接下来呢,每次都都加一嘛,对吧,每一次都是这个爱加加的这种状况啊,然后把每一个当前循环变量的这个值都。
03:04
叠加相乘都乘在一起,得到结果返回就可以了,这是一种方式,就是直接用循环搞定,那另外呢,其实还有一种方式,可以仔细的观察一下我们对于这个阶乘计算的过程啊,比方说五的阶乘。如果说大家能够考虑到前面的这个1234相乘。其实就能发现这样一个规律,就是1234相乘,这不就是四的阶乘吗?哎,所以假如说我已经算出了四的阶乘,那五的阶乘其实非常简单,就是在四的阶乘基础上,在乘以当前的N乘以五不就完了吗?所以我其实可以把这个N的阶乘啊,写成N减一的阶乘。乘以N。哎,所以大家就会看到了,这样的话,我当前计算N的阶乘就变成了。N计算N减一的阶乘啊,所以大家看这个N的阶乘实现的过程是什么呢?这不就是调用自身吗?只不过参数改变了,变成了N减一,那N减一的阶乘又怎么算呢?当然就可以通过N减二来再做计算啊,我们知道四的阶乘又是三的阶乘乘以四嘛。
04:17
哎,所以这样一层一层调用,最后当然应该有一个有一个基准情形,比如说我们这个阶乘啊,三的阶乘再分解成二的阶乘乘以三,那二的阶层再分解成一的阶乘乘以二。一的阶乘我们继续减1N减一嘛,那分解成零的阶乘,乘以一,那要注意零的阶乘,那就不要再减,减成负的了,我们可以直接规定零的阶乘就是一,在这种情况下,不要再去递位调用了,直接返回一就可以了,那不就解决了这个问题吗?啊,得到了零的阶成,就可以反推出一的阶层,二的阶层,三的阶成,四的阶层,最后得到五的阶层。这就是我们两种不同的实现思路,一种是循环,另外一种是递归,接下来我们就可以在代码里边给大家做一个具体的实现啊,那刚才我们分析的这个过程大家也发现了啊,递归的这种实现其实并不依赖到底是函数式编程语言还是非函数式编程语言,那比方说在这个Java里边,我们同样可以实现递归,所以接下来我们首先在Java里边写一个测试的代码来实现阶层的这个功能,我们新建一个Java class,我们主要是要测试归,呃归叫做reccus,把这些写出来,我们方法先写出来,然后我们这里边主要是要去。
05:43
直线一个。计算阶乘的函数,然后来计算阶乘。当然在。画里边我们是把它叫做方法啊,那下面我们先把这个方法写出来吧,有两种实现,一种我们是用圆环,那这个方法我们直接写成public static,切成最终返回的肯定是一个整数,所以是in th。
06:14
就是我们基本的一个声明,在里边我们要传入一个N了,也是计算几的阶层啊,那这里边比方说我们要计算的是接s out打印出来啊,计算的是五的阶层,就是我们当前整体的这个逻辑啊,那里边循环实现的话应该怎么算呢?啊,那就相当于是从一一直乘到N,来一个for循环把它搞定不就完了吗?那这里边我们需要提前定义一个最后要返回的结果,Result,初始值给多少呢?初始值当然应该给一嘛,因为后面要乘,如果给零的话,这个就不对了啊,如果是相加的话,可以给零,这边我们给一个一,接下来就是for循环给一个I,初始是一。然后别数是N小于等于ni加加里面做计算的时候,叠加计算的时候,当然就是每一次都是result,就等于result乘以I啊,当然了大家也可以简写,直接写成乘等于,这样的话,每一次把当前的爱叠加停在里边,最后返回当前的result。
07:25
就是我们计算的结果,我们可以测试一下,看看得到结果对不对。120完全没有问题,这是使用循环的一个实现啊,这个看起来还不算太难啊,就是整体来讲的话非常简单,一个for循环直接搞定了,那接下来呢,我们再来看一看另外一种做法,就是刚才提到的递归实现,递归实现呢?呃,关键在于大家的思路要清晰,是找到一个相当于递归的计算方法,我们现在要计算N的。
08:00
阶乘,那么它其实本质上我们要算的就是N减一的阶乘,再乘以N就完了,哎,所以大家如果把这个搞清楚的话,接下来这个代码可以非常的简单,比方说啊,这个我们就简写,我就叫做吧,同样还是int n为一个参数传进来,那我现在就直接要返回的就是fact n减一阶乘乘以N完事,大家看其实就是这样一个表达,但是这里需要注意就是既然我这里是自己调用自己,你如果无限这么调用的话,那就退不出去了,永远在简一不停的计算,对吧?我们这里如果传入一个五的话,那你要算的就是四的阶乘乘以五,然后四的阶乘呢,就是三的阶乘乘以四,然后就是二的阶乘,一的阶乘,零的阶乘继续减,那变成负一的阶乘,负二的阶乘,这不对了,所以我们说。递归,实现自己自身调用自身,一定要有一个退出的机制,也就是说一定要有一个批准引情景,一准零零,这就是我们说的如果当前的N。
09:12
已经减到了零的话,N等于零的话,那就不要再去减了,不要再去递归N自身了,直接返回一完事了,因为我们说规定零的阶乘就是一嘛,哎,所以大家看之前如果用递归实现的话,代码可以非常简洁,两行直接搞定,就是一行判断基准情形定义零的阶乘等于一对我们可以直接写在这里啊,零的阶乘一。然后另外一行就是我们的推啊,一个关系,当前N的阶乘就等于N减一的阶乘乘以N啊,所以整体来讲的话,显然递归实现要比循环实现啊,就是整体来讲要简单很多啊,代码会简洁很多,当然了,这里边可能需要大家要把这个思路要搞清楚,理解到底是怎么做。
10:05
它本身实现就会更加简单。所以。递归这种作为一种常见的编程手段,编程技巧,在很多算法,很多这个代码里边都会有实际的应用。
我来说两句