详解匿名函数递归:从此能看懂天书代码


最近在读《左耳听风》,里面提到了一个匿名函数递归的例子,觉得很有趣,但是我觉得书里讲解的还是有点难懂,所以尝试用自己的理解把这个问题重新讲了一遍。注:本文中所用的代码示例会同时使用JavaScript,Python语言。

让我们先来看下面这段代码:

1
2
// javascript
(f => f(f))(f => n => n == 0 ? 1 : n*f(f)(n-1))
1
2
# python
(lambda f: f(f))(lambda f: lambda n: 1 if n == 0 else n*f(f)(n-1))

这是一个求阶乘的匿名递归函数,如果你第一次看这样的代码就能看懂,我管保你是个天才!看不懂很正常,别着急,下面我来和你一起破译这段天书代码,揭开它神秘的面纱,不得不说,这里面包含的知识点是很多的。

什么是递归

说到递归,惯例是用求阶乘来作为例子,我们先看一下阶乘的递推公式:

$$
F(n) = n\cdot F(n-1) ;F(0) = 1
$$

递归和数学上的递推公式非常相似,请看下面求阶乘的递归函数代码:

1
2
3
4
// javascript
function F(n) {
return n == 0 ? 1 : n*F(n-1);
}
1
2
3
# python
def F(n):
return 0 if n == 0 else n*F(n-1)

是不是跟上面的数学公式非常像,只不过多了一些函数定义的语句。给递归下一个通俗的定义: 递归就是在一个函数内部自己调用自己。递归有很多好处,可以让代码变得非常简单易懂,而且你能从递归的代码中欣赏到数学公式一样的美。当然,使用递归容易遇到性能问题,这个就不在本文讨论范围之内了。

递归的其他写法

上面的代码都是常规的定义,但如果想理解一个问题的本质,就得多问几个问题,接下来我们思考一个问题:在定义一个函数的时候,函数体内部的代码调用了函数自己,也就是 F(*) 这句代码,F作为一个函数名必须以某种形式被传入到函数体内,否则函数体无法知道它吗,也就无法使用它。在这里它是怎么被传入的?

函数调用的变量类型

类型说明
参数传入通过参数列表传入,在定义的时候是形参,调用的时候传入实参
全局变量函数体外部定义的全局变量。
内部变量在函数体内部定义,定义之后可以调用。

很明显,上面递归函数中的 F 没有在参数列表中,也不是局部变量,那它是不是全局变量呢?好像也不是传统意义上的全局变量,我们只能说:编译器以某种特殊的方式帮助我们把这个问题处理了,调用F类似调用一个全局变量。

接下来继续思考:如果我们抛开上帝视角,假设编译器不会帮我们处理,用我们熟悉的方式来解决这个问题,应该怎么办?从上面的表格不难看出答案:把这个地址以参数(形参)的形式传递到函数体内部,函数体就知道该调用谁了,然后在真正调用的时候再传入实参就可以了。

1
2
3
4
// javascript
function F(f, n) {
return n == 0 ? 1 : n*f(n-1);
}
1
2
3
# python
def F(f,n):
return 1 if n == 0 else n*f(f, n-1)

注意:为了表示区分,代码示例中的形参一律用 f 表示,实参用 F 表示,F代表有定义的函数名,f 只是一个代号。形参和实参的区分十分重要,是帮助我们理解天书代码的关键。

上面这个新的递归函数可以按照如下方式调用:

1
2
F(F, 4)
# 120

因为调用的时候 F 已经被定义了,可以被正确传递到函数体内部。

折腾了半天好像让这个函数的调用更复杂了,下一个问题:我们有没有办法把 F(F, 4) 参数里面的F去掉?

高阶函数

高阶函数是返回值为函数的函数,是函数编程里面很基本的一个概念。因为在函数编程中函数是一等公民,跟普通变量和常量的使用没啥区别,完全可以作为函数的返回值。比如,常用的 power 函数接受两个参数,但如果我只是想求x的平方或者x的立方,每次都传入两个参数好像很麻烦,那么就可以用高阶函数的方式来简化一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
# python
def higherOrder(n):
# n是一个数,表示指数
def power(x):
# x是一个数,返回它的n次方
return x ** n
return power

# 测试代码
square = higherOrder(2) # 调用高阶函数,传入2,返回一个计算平方的函数
cube = higherOrder(3) # 调用高阶函数,传入3,返回一个计算立方的函数
print(square(2)) # 输出4,即2的平方
print(cube(2)) # 输出8,即2的立方

square 和 cube 的调用是不是方便多了? 可见高阶函数的一个用途是:用来减少参数

回归正题,如何把 F(F, 4) 中的 F 去掉呢?不用我说,你已经知道答案了吧。

1
2
3
4
5
6
7
8
9
10
11
12
# 原来的函数
def F(f, n):
return 1 if n == 0 else n*f(f, n-1)

# 用来消除参数的高阶函数
def higherOrder(f):
return lambda n: f(f, n)

# 创建消除参数的新函数
F_ = higherOrder(F)

print(F_(4)) # 输出 24
1
2
3
4
5
6
7
8
9
10
11
function F(f, n) {
return n == 0 ? 1 : n*f(f, n-1);
}

function higherOrder(f) {
return function (n) {
return f(f,n)
};
}
F_ = higherOrder(F)
console.log(F_(4)) // 输出 24

俄罗斯套娃

经过上面一番折腾,我们在调用 F_ 的时候可以只传递一个参数了。不过调用的时候却是层层嵌套,看起来是个俄罗斯套娃:higherOrder里面调用了F,F里面调用了 f,f 在实际调用中又被替换成了 F 自己的地址。

调用的时候确实简单了,但是还得分三个步骤定义,有点复杂,怎么优化一下?

定义函数的时候,每个函数都有了一个名字,这个名字是必须的吗?我们先看下面的代码:

1
2
3
4
5
6
7
# 分步定义再传递参数
x = 3
y = x*6
F(y)

# 一次传入表达式
F(6*3)

一般我们写代码的时候都会避免第一种写法,x和y两个变量名完全没啥用。以此类推,上面例子中定义的 F 和 higherOrder 都不是必须的,可以匿名化。

什么是匿名函数

匿名函数也是函数编程里面很重要的概念,可以类比为一个没有变量名字的表达式。

1
2
3
# python
# 在python里面匿名函数用lambda定义,又叫lambda表达式
lambda x: x + 1
1
2
3
// js
// 在js里面匿名函数用箭头定义,又叫箭头函数
x => x + 1

这就是一个匿名函数,x是参数,冒号后面是函数体,函数名是省略的。我们可以随意把这个匿名函数赋值给一个变量,或者传递给另外一个函数。接下来我们用匿名函数的方式简化上述代码.

匿名函数递归

匿名化改造

1
2
3
4
def F(f, n):
return 1 if n == 0 else n*f(f, n-1)
# 匿名函数①
lambda f,n: 1 if n == 0 else n*f(f, n-1)
1
2
3
4
def higherOrder(f):
return lambda n: f(f, n)
# 匿名函数②
lambda f: lambda n: f(f, n)

像求数学公式一样,把①带入②

1
2
# 匿名函数③
lambda f: lambda: n: 1 if n == 0 else n*f(f)(n-1)

js的代码类似,不再赘述。请注意,在函数①中的形参 f 代表的是求阶乘函数的地址。 f(f, n-1) 的形式代表了我们调用这个函数的方式,在匿名化改造之前,有如下对应关系:

1
f(f, n-1) <-  F(f, n)

改造后,F这个中间函数已经被匿名化了,不存在了,我们将其合并到了 higherOrder(f) 这个函数内部,所以调用方式也需要改变。新的匿名函数没有名字,姑且给一个代号g,g的调用方式和上面的F_(4) = higherOrder(F)(4)具有相同的形式,于是又如下对应关系

1
f(f)(n-1) <-  g(f)(n)

最里面这段递归代码的本质就是调用自己,重新回顾一下我们对递归的通俗定义:递归就是在一个函数内部自己调用自己。原来存在 F 函数的时候,我么用调用 F 的方式,现在函数变成了新的形式,自然也需要用新的形式 调用自己
这就是为什么我们在把①带入②的时候,把 f(f, n-1) 换成了 f(f)(n-1)

再看上面的匿名函数③,确实只有一个函数了,但是我们应该怎么调用这个鬼东西?

这个匿名函数里面的f也是形参,需要从外部传递,但是传递的时候这个实参应该是匿名函数自己的地址。悖论来了,一个没有名字的函数,怎么把自己的地址传递给自己?

自己调用自己

为了让匿名函数实现自己调用自己,我们不得不再使用一个技巧,继续俄罗斯套娃。

俄罗斯套完

1
2
// js
f => f(f)
1
2
# python
lambda f: f(f)

注意,上面两个匿名函数里,f全部都是形参,在调用的时候才传入实际的地址。这个函数接受一个函数参数,然后在函数体内部自己调用了自己,这个方式有点tricky,但也很简洁。把上面的匿名函数③以参数的形式传递给这个套娃函数,就得到了如下的代码。

1
2
# python
(lambda f: f(f))(lambda f: lambda n: 1 if n == 0 else n*f(f)(n-1))
1
2
# js
(f => f(f))(f => n => n == 0 ? 1 : n*f(f)(n-1))

js的代码看起来更简洁一些呢。

1
2
3
# 把这个匿名函数随便赋值给一个变量
g = (lambda f: f(f))(lambda f: lambda n: 1 if n == 0 else n*f(f, n-1))
print(g(4)) # 120 阶乘
大功告成!

总结

第一部分代码:匿名函数实现自己调用自己的技巧。

1
2
// js
(f => f(f))

第二部分代码:利用高阶函数返回一个函数,可以减少调用时候传入参数的个数。

1
2
// js
(f => n => ***)

第三部分代码:真正的计算逻辑。

1
2
// js
n == 0 ? 1 : n*f(f)(n-1)

第一部分和第二部分的逻辑是通用的,如果你想把一个递归函数进行匿名化改造,只需要添加第一段和第二段代码即可,第三段代码和你在其他函数里面写的没有什么区别,只需要把递归调用的方式变一下:

1
2
3
4
// 非匿名函数递归的代码片段
n == 0 ? 1 : n*f(n-1)
// 匿名函数递归的代码片段
n == 0 ? 1 : n*f(f)(n-1)

从f到f(f),密码就是套娃!


详解匿名函数递归:从此能看懂天书代码
http://yoursite.com/posts/1793/
作者
海鹏
发布于
2024年1月18日
许可协议