最近在讀《左耳聽(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)注我焰坪，非常感謝！