最近在讀《左耳聽(tīng)風(fēng)》，里面提到了一個(gè)匿名函數(shù)遞歸的例子，覺(jué)得很有趣，但是我覺(jué)得書(shū)里講解的還是有點(diǎn)難懂，所以嘗試用自己的理解把這個(gè)問(wèn)題重新講了一遍。注：本文中所用的代碼示例會(huì)同時(shí)使用JavaScript，Python語(yǔ)言。

讓我們先來(lái)看下面這段代碼：

// javascript
(f => f(f))(f => n => n == 0 ? 1 : n*f(f)(n-1))

# python
(lambda f: f(f))(lambda f: lambda n: 1 if n == 0 else n*f(f)(n-1))

這是一個(gè)求階乘的匿名遞歸函數(shù)，如果你第一次看這樣的代碼就能看懂，我管保你是個(gè)天才！看不懂很正常，別著急，下面我來(lái)和你一起破譯這段天書(shū)代碼，揭開(kāi)它神秘的面紗，不得不說(shuō)，這里面包含的知識(shí)點(diǎn)是很多的。

什么是遞歸

說(shuō)到遞歸，慣例是用求階乘來(lái)作為例子，我們先看一下階乘的遞推公式：

遞歸和數(shù)學(xué)上的遞推公式非常相似，請(qǐng)看下面求階乘的遞歸函數(shù)代碼：

// javascript
function F(n) {
    return n == 0 ? 1 : n*F(n-1);
}

# python
def F(n):
    return 0 if n == 0 else n*F(n-1)

是不是跟上面的數(shù)學(xué)公式非常像，只不過(guò)多了一些函數(shù)定義的語(yǔ)句。給遞歸下一個(gè)通俗的定義： 遞歸就是在一個(gè)函數(shù)內(nèi)部自己調(diào)用自己。遞歸有很多好處，可以讓代碼變得非常簡(jiǎn)單易懂，而且你能從遞歸的代碼中欣賞到數(shù)學(xué)公式一樣的美。當(dāng)然，使用遞歸容易遇到性能問(wèn)題，這個(gè)就不在本文討論范圍之內(nèi)了。

遞歸的其他寫(xiě)法

上面的代碼都是常規(guī)的定義，但如果想理解一個(gè)問(wèn)題的本質(zhì)，就得多問(wèn)幾個(gè)問(wèn)題，接下來(lái)我們思考一個(gè)問(wèn)題：在定義一個(gè)函數(shù)的時(shí)候，函數(shù)體內(nèi)部的代碼調(diào)用了函數(shù)自己，也就是 F(*) 這句代碼，F(xiàn)作為一個(gè)函數(shù)名必須以某種形式被傳入到函數(shù)體內(nèi)，否則函數(shù)體無(wú)法知道它嗎，也就無(wú)法使用它。在這里它是怎么被傳入的？

函數(shù)調(diào)用的變量類(lèi)型

很明顯，上面遞歸函數(shù)中的 F 沒(méi)有在參數(shù)列表中，也不是局部變量，那它是不是全局變量呢？好像也不是傳統(tǒng)意義上的全局變量，我們只能說(shuō)：編譯器以某種特殊的方式幫助我們把這個(gè)問(wèn)題處理了，調(diào)用F類(lèi)似調(diào)用一個(gè)全局變量。

接下來(lái)繼續(xù)思考：如果我們拋開(kāi)上帝視角，假設(shè)編譯器不會(huì)幫我們處理，用我們熟悉的方式來(lái)解決這個(gè)問(wèn)題，應(yīng)該怎么辦？從上面的表格不難看出答案：把這個(gè)地址以參數(shù)（形參）的形式傳遞到函數(shù)體內(nèi)部，函數(shù)體就知道該調(diào)用誰(shuí)了，然后在真正調(diào)用的時(shí)候再傳入實(shí)參就可以了。

// javascript
function F(f, n) {
    return n == 0 ? 1 : n*f(n-1);
}

# python
def F(f,n):
    return 1 if n == 0 else n*f(f, n-1)

注意：為了表示區(qū)分，代碼示例中的形參一律用 f 表示，實(shí)參用 F 表示，F(xiàn)代表有定義的函數(shù)名，f 只是一個(gè)代號(hào)。形參和實(shí)參的區(qū)分十分重要，是幫助我們理解天書(shū)代碼的關(guān)鍵。

上面這個(gè)新的遞歸函數(shù)可以按照如下方式調(diào)用：

F(F, 4)
# 120

因?yàn)檎{(diào)用的時(shí)候 F 已經(jīng)被定義了，可以被正確傳遞到函數(shù)體內(nèi)部。

折騰了半天好像讓這個(gè)函數(shù)的調(diào)用更復(fù)雜了，下一個(gè)問(wèn)題：我們有沒(méi)有辦法把 F(F, 4) 參數(shù)里面的F去掉？

高階函數(shù)

高階函數(shù)是返回值為函數(shù)的函數(shù)，是函數(shù)編程里面很基本的一個(gè)概念。因?yàn)樵诤瘮?shù)編程中函數(shù)是一等公民，跟普通變量和常量的使用沒(méi)啥區(qū)別，完全可以作為函數(shù)的返回值。比如，常用的 power 函數(shù)接受兩個(gè)參數(shù)，但如果我只是想求x的平方或者x的立方，每次都傳入兩個(gè)參數(shù)好像很麻煩，那么就可以用高階函數(shù)的方式來(lái)簡(jiǎn)化一下：

# python
def higherOrder(n):
  # n是一個(gè)數(shù)，表示指數(shù)
  def power(x):
    # x是一個(gè)數(shù)，返回它的n次方
    return x ** n
  return power

# 測(cè)試代碼
square = higherOrder(2) # 調(diào)用高階函數(shù)，傳入2，返回一個(gè)計(jì)算平方的函數(shù)
cube = higherOrder(3) # 調(diào)用高階函數(shù)，傳入3，返回一個(gè)計(jì)算立方的函數(shù)
print(square(2)) # 輸出4，即2的平方
print(cube(2)) # 輸出8，即2的立方

square 和 cube 的調(diào)用是不是方便多了？ 可見(jiàn)高階函數(shù)的一個(gè)用途是：用來(lái)減少參數(shù)。

回歸正題，如何把 F(F, 4) 中的 F 去掉呢？不用我說(shuō)，你已經(jīng)知道答案了吧。

# 原來(lái)的函數(shù)
def F(f, n):
    return 1 if n == 0 else n*f(f, n-1)

# 用來(lái)消除參數(shù)的高階函數(shù)
def higherOrder(f):
    return lambda n: f(f, n)

# 創(chuàng)建消除參數(shù)的新函數(shù)
F_ = higherOrder(F)

print(F_(4)) # 輸出 24

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

俄羅斯套娃

經(jīng)過(guò)上面一番折騰，我們?cè)谡{(diào)用 F_ 的時(shí)候可以只傳遞一個(gè)參數(shù)了。不過(guò)調(diào)用的時(shí)候卻是層層嵌套，看起來(lái)是個(gè)俄羅斯套娃：higherOrder里面調(diào)用了F，F(xiàn)里面調(diào)用了 f，f 在實(shí)際調(diào)用中又被替換成了 F 自己的地址。

調(diào)用的時(shí)候確實(shí)簡(jiǎn)單了，但是還得分三個(gè)步驟定義，有點(diǎn)復(fù)雜，怎么優(yōu)化一下？

定義函數(shù)的時(shí)候，每個(gè)函數(shù)都有了一個(gè)名字，這個(gè)名字是必須的嗎？我們先看下面的代碼：

# 分步定義再傳遞參數(shù)
x = 3
y = x*6
F(y)

# 一次傳入表達(dá)式
F(6*3)

一般我們寫(xiě)代碼的時(shí)候都會(huì)避免第一種寫(xiě)法，x和y兩個(gè)變量名完全沒(méi)啥用。以此類(lèi)推，上面例子中定義的 F 和 higherOrder 都不是必須的，可以匿名化。

什么是匿名函數(shù)

匿名函數(shù)也是函數(shù)編程里面很重要的概念，可以類(lèi)比為一個(gè)沒(méi)有變量名字的表達(dá)式。

# python
# 在python里面匿名函數(shù)用lambda定義，又叫l(wèi)ambda表達(dá)式
lambda x: x + 1

// js
// 在js里面匿名函數(shù)用箭頭定義，又叫箭頭函數(shù)
x => x + 1

這就是一個(gè)匿名函數(shù)，x是參數(shù)，冒號(hào)后面是函數(shù)體，函數(shù)名是省略的。我們可以隨意把這個(gè)匿名函數(shù)賦值給一個(gè)變量，或者傳遞給另外一個(gè)函數(shù)。接下來(lái)我們用匿名函數(shù)的方式簡(jiǎn)化上述代碼.

匿名函數(shù)遞歸

匿名化改造

def F(f, n):
    return 1 if n == 0 else n*f(f, n-1)
# 匿名函數(shù)①
lambda f,n: 1 if n == 0 else n*f(f, n-1)

def higherOrder(f):
    return lambda n: f(f, n)
# 匿名函數(shù)②
lambda f: lambda n: f(f, n)

像求數(shù)學(xué)公式一樣，把①帶入②

# 匿名函數(shù)③
lambda f: lambda: n: 1 if n == 0 else n*f(f)(n-1)

js的代碼類(lèi)似，不再贅述。請(qǐng)注意，在函數(shù)①中的形參 f 代表的是求階乘函數(shù)的地址。 f(f, n-1) 的形式代表了我們調(diào)用這個(gè)函數(shù)的方式，在匿名化改造之前，有如下對(duì)應(yīng)關(guān)系：

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

改造后，F(xiàn)這個(gè)中間函數(shù)已經(jīng)被匿名化了，不存在了，我們將其合并到了 higherOrder(f) 這個(gè)函數(shù)內(nèi)部，所以調(diào)用方式也需要改變。新的匿名函數(shù)沒(méi)有名字，姑且給一個(gè)代號(hào)g，g的調(diào)用方式和上面的F_(4) = higherOrder(F)(4)具有相同的形式，于是又如下對(duì)應(yīng)關(guān)系

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

最里面這段遞歸代碼的本質(zhì)就是調(diào)用自己，重新回顧一下我們對(duì)遞歸的通俗定義：遞歸就是在一個(gè)函數(shù)內(nèi)部自己調(diào)用自己。原來(lái)存在 F 函數(shù)的時(shí)候，我么用調(diào)用 F 的方式，現(xiàn)在函數(shù)變成了新的形式，自然也需要用新的形式 調(diào)用自己。
這就是為什么我們?cè)诎癣賻擘诘臅r(shí)候，把 f(f, n-1) 換成了 f(f)(n-1)。

再看上面的匿名函數(shù)③，確實(shí)只有一個(gè)函數(shù)了，但是我們應(yīng)該怎么調(diào)用這個(gè)鬼東西？

這個(gè)匿名函數(shù)里面的f也是形參，需要從外部傳遞，但是傳遞的時(shí)候這個(gè)實(shí)參應(yīng)該是匿名函數(shù)自己的地址。悖論來(lái)了，一個(gè)沒(méi)有名字的函數(shù)，怎么把自己的地址傳遞給自己？

自己調(diào)用自己

為了讓匿名函數(shù)實(shí)現(xiàn)自己調(diào)用自己，我們不得不再使用一個(gè)技巧，繼續(xù)俄羅斯套娃。

俄羅斯套完

// js
f => f(f)

# python
lambda f: f(f)

注意，上面兩個(gè)匿名函數(shù)里，f全部都是形參，在調(diào)用的時(shí)候才傳入實(shí)際的地址。這個(gè)函數(shù)接受一個(gè)函數(shù)參數(shù)，然后在函數(shù)體內(nèi)部自己調(diào)用了自己，這個(gè)方式有點(diǎn)tricky，但也很簡(jiǎn)潔。把上面的匿名函數(shù)③以參數(shù)的形式傳遞給這個(gè)套娃函數(shù)，就得到了如下的代碼。

# python
(lambda f: f(f))(lambda f: lambda n: 1 if n == 0 else n*f(f)(n-1))

# js
(f => f(f))(f => n => n == 0 ? 1 : n*f(f)(n-1))

js的代碼看起來(lái)更簡(jiǎn)潔一些呢。

# 把這個(gè)匿名函數(shù)隨便賦值給一個(gè)變量
g = (lambda f: f(f))(lambda f: lambda n: 1 if n == 0 else n*f(f, n-1))
print(g(4)) # 120 階乘

大功告成！

總結(jié)

第一部分代碼：匿名函數(shù)實(shí)現(xiàn)自己調(diào)用自己的技巧。

// js
(f => f(f))

第二部分代碼：利用高階函數(shù)返回一個(gè)函數(shù)，可以減少調(diào)用時(shí)候傳入?yún)?shù)的個(gè)數(shù)。

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

第三部分代碼：真正的計(jì)算邏輯。

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

第一部分和第二部分的邏輯是通用的，如果你想把一個(gè)遞歸函數(shù)進(jìn)行匿名化改造，只需要添加第一段和第二段代碼即可，第三段代碼和你在其他函數(shù)里面寫(xiě)的沒(méi)有什么區(qū)別，只需要把遞歸調(diào)用的方式變一下：

// 非匿名函數(shù)遞歸的代碼片段
n == 0 ? 1 : n*f(n-1)
// 匿名函數(shù)遞歸的代碼片段
n == 0 ? 1 : n*f(f)(n-1)

從f到f(f)，密碼就是套娃！

如果你喜歡我的文章，歡迎到我的個(gè)人網(wǎng)站關(guān)注我，非常感謝！