递归函数

今天要讲的不是某一个函数,而是一个非常重要的思想——递归。
这部分内容非常难,所以请做好准备,看不懂也没关系,非必须掌握,有兴趣就一起研究。

在函数内部,可以调用其他函数,比如fx=(x)=>Text.From(x)&"个",定义了一个函数fx,调用了另一个函数Text.From
如果一个函数在内部调用自身本身,这个函数就是递归函数。
用我们中学学过的阶乘来打个比方,在工作表函数里有个fact表示阶乘:
fact(n)=n!=1*2*3*(n-1)*n=(n-1)!*n=fact(n-1)*n
由上可以推导出fact(n)=fact(n-1)*n,只有n=1时需特殊处理,翻译成M语言就是:
fact = (n)=> if n=1 then 1 else @fact(n-1)*n
我们知道在一般情况下,如果之前没有定义变量而直接使用的话,那么一定会出现"无法识别名称fact"之类的报错提示。

@是作用域操作符,引用函数在其范围内,简单来说就是允许函数再次调用本身,从而实现递归。
分解来看下过程:

=>fact(5)
=>fact(4)*5
=>fact(3)*4*5
=>fact(2)*3*4*5
=>fact(1)*2*3*4*5
=>1*2*3*4*5
=>120

也是像剥洋葱一样一层一层的,是不是很类似之前的List.Accumulate
没错,我们之前说过acc就相当于循环,理论上所有的递归都能改写成循环,但递归的优势在于写法简洁,逻辑清晰。
初步了解了递归思想,那我们可以用来解决什么问题呢?

现有客户20000人,每天流失30%,但会再新增10000,问30天后还有多少客户?
先模拟下,第1天流失30%,那就是剩下0.7*20000+10000,第2天就是((0.7*20000)+10000)*0.7+10000,依此类推。
可以想象如果没有递归或者循环,那30天后的公式是不是得写好长好长,用递归就清晰多了:

let
    fx = (n,d)=>[f=0.7*n+10000,r=if d=1 then f else @fx(f,d-1)][r],
    result = fx(20000,30)
in
    result

n表示初始值有多少人,d表示天数。
同循环一样,递归也要有一个终止条件,否则就是死循环,比如fx = (x)=>@fx(x+1),无限循环下去肯定没有结果,所以一般都会在最前面使用if作为条件判断。

之前在acc那一篇中讲过构建斐波那契数列,当然用递归也能做。
斐波那契数列就是1,1,2,3,5,8,13,21,34...从第3项开始,每一项等于前两项的和。现要求使用递归函数实现求数列中第n项是多少?
我们现在试着把上面一行字翻译成M语言:
每一项等于前两项的和,也就是第n项=第n-2项+第n-1项,假设函数名为fx,那么fx(n)=fx(n-2)+fx(n-1)。
又因为这个规律从第3项开始,前2项为特殊值都是1,所以完整的公式为fx = (n)=>if n<=2 then 1 else @fx(n-2)+@fx(n-1)
几乎没有任何思考公式就写完了,完全遵循我们的思维逻辑。
一个非常经典的递归问题,如果你看懂了,那么恭喜你已经get到了递归的核心思想。

很简单对吧,继续加大难度。之前写过一篇《汉诺塔经典递归问题》,再拿出来探讨下。
汉诺塔游戏大家都玩过,有三座塔ABC,A上有若干个大小不等的盘子,大盘在下小盘在上,需要把这些盘子从A移到C,中间可以借用B但每次只能允许移动一个盘子,并且在移动过程中,3座塔上的盘子始终保持大盘在下小盘在上。
简化下问题:把A上的n个盘子移动到C,可以借助B。
首先假设有n个盘子编号分别为1..n,初始状态为A:按顺序摆放n个盘子,B:空的,C:空的。我们要把A上的n个盘子移到C,所以最终C最下面应该就是编号为n的最大的盘子,那要取得最大的n,是不是要先把A上面的n-1个盘子移开,移开放哪里?肯定不是A,是C么?移到C的话n就没地方放了,那就先放到B。你可能会问怎么移,不是一次只能移动一个盘子么?你可以看成是一个函数实现,先不要管如何实现的,这是理解递归的第一个重点。
至此完成了第一步,此时状态为A:最大的盘子n,B:按顺序摆放n-1个盘子,C:空的。那么这时候就可以进行第二步,把A上最大的盘子n移到C,此时的状态为A:空的,B:按顺序摆放n-1个盘子,C:最大的盘子n。而C上只有一个最大的盘子n,那么就可以把C看成空的,因为任何盘子都可以放到C,这是第二个重点。所以此时的状态为A:空的,B:按顺序摆放n-1个盘子,C:空的
所以第三步,我们只需要再把B上的n-1个盘子移到A,变成A:n-1个盘子,B:空的,C:空的,那么问题就回到了初始状态,只是盘子的个数由n变成了n-1。同样,先不用管是如何实现的。
经过上面三个步骤,我们已经完成了一次递归。每递归一次,A上的盘子就会少一个,直到A上只剩1个最小的盘子,把它从A移到C,递归结束,所有的盘子也都顺利的从A移到了C。写成M语言就是:

let
    move = (n,a,b,c)=>if n=1 then {a&"->"&c} else @move(n-1,a,c,b) & @move(1,a,b,c) & @move(n-1,b,a,c),
    result = move(6, "A", "B", "C")         //测试当A上有6个盘子时的结果
in
    result

从以上的几个案例我们可以发现,要理解递归,我们不用太关心实现的细节,只要看成是由一个函数实现的就行,如果一直纠结怎么把n-1个盘子从A移到B,那么无论如何都理解不了。
再举几个例子来加深理解,其中部分例子之前在acc那篇讲过就不重复描述了,以下案例由畅心提供:

最大公因数:

fx=(x,y)=>if y=0 then x else @fx(y,Number.Mod(x,y)) //测试:fx(72,42)=6

约瑟夫环问题:

fx=(x,y)=>if x=1 then 0 else Number.Mod(@fx(x-1,y)+y,x) //测试:fx(12,1)+1=11

质数判断问题::

fx=(x,y)=>if x=y then 1 else (if Number.Mod(x,y)=0 then 0 else @fx(x,y+1)) //测试:fx(17,2)=1,即17是质数

十进制转二进制:

fx=(x)=>if x/2>=1 then @fx(Number.IntegerDivide(x,2))&Text.From(Number.Mod(x,2)) else "1" //测试:fx(100)=1100100

附件

20 Replies to “递归函数”

    1. 定义函数,左边是变量,右边是表达式。这篇非常难,你可以先看http://pqfans.com/526.html。

  1. 老师,请教一下fx = (n,d)=>[f=0.7*n+10000,r=if d=1 then f else @fx(f,d-1)][r] 这句末尾那个[r]是什么意义,谢谢

    1. 深化,前面的record中有f和r两个字段,[r]取出其中的一个字段。
      参考http://pqfans.com/452.html

  2. 今天收集M语言资料回头来看看,发现能学到不少,有个问题,我测试了下斐波那契数据,fx(3)结果是5,楼主可以测试下,输出结果不对

  3. 真的要自己动手写一下。
    开始是能看懂,一动手完全不知从哪里开始,写了N遍之后才能摸到门。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注