详解匿名函数递归:从此能看懂天书代码
最近在读《左耳听风》,里面提到了一个匿名函数递归的例子,觉得很有趣,但是我觉得书里讲解的还是有点难懂,所以尝试用自己的理解把这个问题重新讲了一遍。注:本文中所用的代码示例会同时使用JavaScript,Python语言。
让我们先来看下面这段代码:
1 |
|
1 |
|
这是一个求阶乘的匿名递归函数,如果你第一次看这样的代码就能看懂,我管保你是个天才!看不懂很正常,别着急,下面我来和你一起破译这段天书代码,揭开它神秘的面纱,不得不说,这里面包含的知识点是很多的。
什么是递归
说到递归,惯例是用求阶乘来作为例子,我们先看一下阶乘的递推公式:
$$
F(n) = n\cdot F(n-1) ;F(0) = 1
$$
递归和数学上的递推公式非常相似,请看下面求阶乘的递归函数代码:
1 |
|
1 |
|
是不是跟上面的数学公式非常像,只不过多了一些函数定义的语句。给递归下一个通俗的定义: 递归就是在一个函数内部自己调用自己。递归有很多好处,可以让代码变得非常简单易懂,而且你能从递归的代码中欣赏到数学公式一样的美。当然,使用递归容易遇到性能问题,这个就不在本文讨论范围之内了。
递归的其他写法
上面的代码都是常规的定义,但如果想理解一个问题的本质,就得多问几个问题,接下来我们思考一个问题:在定义一个函数的时候,函数体内部的代码调用了函数自己,也就是 F(*) 这句代码,F作为一个函数名必须以某种形式被传入到函数体内,否则函数体无法知道它吗,也就无法使用它。在这里它是怎么被传入的?
函数调用的变量类型
类型 | 说明 |
---|---|
参数传入 | 通过参数列表传入,在定义的时候是形参,调用的时候传入实参。 |
全局变量 | 函数体外部定义的全局变量。 |
内部变量 | 在函数体内部定义,定义之后可以调用。 |
很明显,上面递归函数中的 F 没有在参数列表中,也不是局部变量,那它是不是全局变量呢?好像也不是传统意义上的全局变量,我们只能说:编译器以某种特殊的方式帮助我们把这个问题处理了,调用F类似调用一个全局变量。
接下来继续思考:如果我们抛开上帝视角,假设编译器不会帮我们处理,用我们熟悉的方式来解决这个问题,应该怎么办?从上面的表格不难看出答案:把这个地址以参数(形参)的形式传递到函数体内部,函数体就知道该调用谁了,然后在真正调用的时候再传入实参就可以了。
1 |
|
1 |
|
注意:为了表示区分,代码示例中的形参一律用 f 表示,实参用 F 表示,F代表有定义的函数名,f 只是一个代号。形参和实参的区分十分重要,是帮助我们理解天书代码的关键。
上面这个新的递归函数可以按照如下方式调用:
1 |
|
因为调用的时候 F 已经被定义了,可以被正确传递到函数体内部。
折腾了半天好像让这个函数的调用更复杂了,下一个问题:我们有没有办法把 F(F, 4) 参数里面的F去掉?
高阶函数
高阶函数是返回值为函数的函数,是函数编程里面很基本的一个概念。因为在函数编程中函数是一等公民,跟普通变量和常量的使用没啥区别,完全可以作为函数的返回值。比如,常用的 power 函数接受两个参数,但如果我只是想求x的平方或者x的立方,每次都传入两个参数好像很麻烦,那么就可以用高阶函数的方式来简化一下:
1 |
|
square 和 cube 的调用是不是方便多了? 可见高阶函数的一个用途是:用来减少参数。
回归正题,如何把 F(F, 4) 中的 F 去掉呢?不用我说,你已经知道答案了吧。
1 |
|
1 |
|
俄罗斯套娃
经过上面一番折腾,我们在调用 F_ 的时候可以只传递一个参数了。不过调用的时候却是层层嵌套,看起来是个俄罗斯套娃:higherOrder里面调用了F,F里面调用了 f,f 在实际调用中又被替换成了 F 自己的地址。
调用的时候确实简单了,但是还得分三个步骤定义,有点复杂,怎么优化一下?
定义函数的时候,每个函数都有了一个名字,这个名字是必须的吗?我们先看下面的代码:
1 |
|
一般我们写代码的时候都会避免第一种写法,x和y两个变量名完全没啥用。以此类推,上面例子中定义的 F 和 higherOrder 都不是必须的,可以匿名化。
什么是匿名函数
匿名函数也是函数编程里面很重要的概念,可以类比为一个没有变量名字的表达式。
1 |
|
1 |
|
这就是一个匿名函数,x是参数,冒号后面是函数体,函数名是省略的。我们可以随意把这个匿名函数赋值给一个变量,或者传递给另外一个函数。接下来我们用匿名函数的方式简化上述代码.
匿名函数递归
匿名化改造
1 |
|
1 |
|
像求数学公式一样,把①带入②
1 |
|
js的代码类似,不再赘述。请注意,在函数①中的形参 f 代表的是求阶乘函数的地址。 f(f, n-1) 的形式代表了我们调用这个函数的方式,在匿名化改造之前,有如下对应关系:
1 |
|
改造后,F这个中间函数已经被匿名化了,不存在了,我们将其合并到了 higherOrder(f) 这个函数内部,所以调用方式也需要改变。新的匿名函数没有名字,姑且给一个代号g,g的调用方式和上面的F_(4) = higherOrder(F)(4)具有相同的形式,于是又如下对应关系
1 |
|
最里面这段递归代码的本质就是调用自己,重新回顾一下我们对递归的通俗定义:递归就是在一个函数内部自己调用自己。原来存在 F 函数的时候,我么用调用 F 的方式,现在函数变成了新的形式,自然也需要用新的形式 调用自己。
这就是为什么我们在把①带入②的时候,把 f(f, n-1) 换成了 f(f)(n-1)。
再看上面的匿名函数③,确实只有一个函数了,但是我们应该怎么调用这个鬼东西?
这个匿名函数里面的f也是形参,需要从外部传递,但是传递的时候这个实参应该是匿名函数自己的地址。悖论来了,一个没有名字的函数,怎么把自己的地址传递给自己?
自己调用自己
为了让匿名函数实现自己调用自己,我们不得不再使用一个技巧,继续俄罗斯套娃。
1 |
|
1 |
|
注意,上面两个匿名函数里,f全部都是形参,在调用的时候才传入实际的地址。这个函数接受一个函数参数,然后在函数体内部自己调用了自己,这个方式有点tricky,但也很简洁。把上面的匿名函数③以参数的形式传递给这个套娃函数,就得到了如下的代码。
1 |
|
1 |
|
js的代码看起来更简洁一些呢。
1 |
|
大功告成!
总结
第一部分代码:匿名函数实现自己调用自己的技巧。
1 |
|
第二部分代码:利用高阶函数返回一个函数,可以减少调用时候传入参数的个数。
1 |
|
第三部分代码:真正的计算逻辑。
1 |
|
第一部分和第二部分的逻辑是通用的,如果你想把一个递归函数进行匿名化改造,只需要添加第一段和第二段代码即可,第三段代码和你在其他函数里面写的没有什么区别,只需要把递归调用的方式变一下:
1 |
|
从f到f(f),密码就是套娃!