JavaScript 中匿名函數的遞歸呼叫的程式碼詳細介紹

不管是什麼程式語言，相信稍微寫過幾行程式碼的同學，對遞迴都不會陌生。 以一個簡單的階乘計算為例：

function factorial(n) {  
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

我們可以看出，遞迴就是在函數內部呼叫對自身的呼叫。 那麼問題來了，我們知道在Javascript中，有一類函數叫做匿名函數，沒有名稱，要怎麼呼叫呢？當然你可以說，可以把匿名函數賦值給一個常數：

const factorial = function(n){  
     if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

這當然是可以的。但是對於某些像，當函數編寫時並不知道自己將要賦值給一個明確的變數的情況時，就會遇到麻煩了。如：

(function(f){
    f(10);
})(function(n){
     if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n-1);//太依赖于上下文变量名
    }
})
//Uncaught ReferenceError: factorial is not defined(…)

那麼存不存在一種完全不需要這種給予準確函數名稱(函數引用變數名稱)的方式呢？

arguments.callee

我們知道在任何一個function內部，都可以存取到一個叫做arguments的變數。

(function(){console.dir(arguments)})(1,2)

列印出這個arguments變數的細節，可以看出他是Arguments的一個實例，而且從資料結構上來講，他是一個類別數組。他除了類別數組的元素成員和length屬性外，還有一個callee方法。 那麼這個callee方法是做什麼的呢？我們來看MDN

callee 是 arguments 物件的屬性。在該函數的函數體內，它可以指向目前正在執行的函數。當函數是匿名函數時，這是很有用的， 例如沒有名字的函數表達式 (也被叫做”匿名函數”)。

哈哈，很明顯這就是我們想要的。接下來就是：

(function(f){
    console.log(f(10));
})(function(n){
     if (n <= 1) {
        return 1;
    } else {
        return n * arguments.callee(n-1);
    }
})
//output: 3628800

但是還有一個問題，MDN的文檔裡明確指出

警告：在ECMAScript 第五版(ES5) 的嚴格模式中禁止使用arguments.callee()。

哎呀，原來在ES5的use strict;中不給用啊，那麼在ES6中，我們換個ES6的arrow function寫寫看：

((f) => console.log(f(10)))(
    (n) => n <= 1? 1: arguments.callee(n-1))
//Uncaught ReferenceError: arguments is not defined(…)

有一定ES6基礎的同學，估計老早就想說了，箭頭函數就是個簡寫形式的函數表達式，並且它擁有詞法作用域的this值（即不會新產生自己作用域下的this, arguments, super 和 new.target等物件），且都是匿名的。

那怎麼辦呢？嘿嘿，我們需要藉用一點FP的想法了。

Y組合子

關於Y Combinator的文章可謂數不勝數，這個由師從希爾伯特的著名邏輯學家Haskell B.Curry（Haskell語言就是以他命名的，而函數式程式語言裡面的Curry手法也是以他命名）「發明」出來的組合算子（Haskell是研究組合邏輯(combinatory logic)的）彷彿有種神奇的魔力，它能夠算出給定lambda表達式（函數）的不動點。從而使得遞迴成為可能。

這裡需要告知一個概念不動點組合子：

#不動點組合子（英文：Fixed-point combinator，或不動點算子）是計算其他函數的一個不動點的高階函數。

函數f的不動點是一個值x使得f(x) = x。例如，0和1是函數 f(x) = x^2 的不動點，因為 0^2 = 0而 1^2 = 1。鑑於一階函數（在簡單值例如整數上的函數）的不動點是個一階值，高階函數f的不動點是另一個函數g使得f(g) = g。那麼，不動點算子是任何函數fix使得對任何函數f都有

f(fix(f)) = fix(f). 不動點組合子允許定義匿名的遞歸函數。它們可以用非遞歸的lambda抽象來定義.

在無型別lambda演算中眾所周知的（可能是最簡單的）不動點組合子叫做Y組合子。

接下來，我們透過一定的演算推到下這個Y組合子。

// 首先我们定义这样一个可以用作求阶乘的递归函数
const fact = (n) => n<=1?1:n*fact(n-1)  
console.log(fact(5)) //120

// 既然不让这个函数有名字，我们就先给这个递归方法一个叫做self的代号
// 首先是一个接受这个递归函数作为参数的一个高阶函数
const fact_gen = (self) => (n) => n<=1?1:n*self(n-1)  
console.log(fact_gen(fact)(5)) //120

// 我们是将递归方法和参数n，都传入递归方法，得到这样一个函数
const fact1 = (self, n) => n<=1?1:n*self(self, n-1)  
console.log(fact1(fact1, 5)) //120

// 我们将fact1 柯理化，得到fact2
const fact2 = (self) => (n) => n<=1?1:n*self(self)(n-1)  
console.log(fact2(fact2)(5)) //120

// 惊喜的事发生了，如果我们将self(self)看做一个整体
// 作为参数传入一个新的函数: (g)=> n<= 1? 1: n*g(n-1)
const fact3 = (self) => (n) => ((g)=>n <= 1?1:n*g(n-1))(self(self))  
console.log(fact3(fact3)(5)) //120

// fact3 还有一个问题是这个新抽离出来的函数，是上下文有关的
// 他依赖于上文的n, 所以我们将n作为新的参数
// 重新构造出这么一个函数: (g) => (m) => m<=1?1:m*g(m-1)
const fact4 = (self) => (n) => ((g) => (m) => m<=1?1:m*g(m-1))(self(self))(n)  
console.log(fact4(fact4)(5))

// 很明显fact4中的(g) => (m) => m<=1?1:m*g(m-1) 就是 fact_gen
// 这就很有意思啦，这个fact_gen上下文无关了, 可以作为参数传入了
const weirdFunc = (func_gen) => (self) => (n) => func_gen(self(self))(n)  
console.log(weirdFunc(fact_gen)(weirdFunc(fact_gen))(5)) //120

// 此时我们就得到了一种Y组合子的形式了
const Y_ = (gen) => (f) => (n)=> gen(f(f))(n)

// 构造一个阶乘递归也很easy了
const factorial = Y_(fact_gen)  
console.log(factorial(factorial)(5)) //120

// 但上面这个factorial并不是我们想要的
// 只是一种fact2,fact3,fact4的形式
// 我们肯定希望这个函数的调用是factorial(5)
// 没问题，我们只需要把定义一个 f&#39; = f(f) = (f)=>f(f)
// eg. const factorial = fact2(fact2)
const Y = gen => n => (f=>f(f))(gen)(n)  
console.log(Y(fact2)(5)) //120  
console.log(Y(fact3)(5)) //120  
console.log(Y(fact4)(5)) //120

推導到這裡，是不是已經感覺到脊背嗖涼了一下，反正筆者我第一次接觸在康托爾、哥德爾、圖靈——永恆的金色對角線這篇文章裡接觸到的時候，整個人瞬間被這種以數學語言去表示程式的方式所折服。

來，我們回想下，我們最終是不是得到了一個不定點算子，這個算子可以找出一個高階函數的不動點f(Y(f)) = Y (f)。 將一個函數傳入一個算子(函數)，得到一個跟自己功能一樣，但又並不是自己的函數，這個說法有些拗口，但又味道十足。

好了，我們回到最初的問題，要怎麼完成匿名函數的遞迴呢？有了Y組合子就很簡單了：

/*求不动点*/
(f => f(f))
/*以不动点为参数的递归函数*/
(fact => n => n <= 1 ? 1 : n * fact(fact)(n - 1)) 
/*递归函数参数*/ 
(5)
// 120

曾经看到过一些说法是”最让人沮丧是，当你推导出它(Y组合子)后，完全没法儿通过只看它一眼就说出它到底是想干嘛”，而我恰恰认为这就是函数式编程的魅力，也是数学的魅力所在，精简优雅的公式，背后隐藏着复杂有趣的推导过程。

总结

务实点儿讲，匿名函数的递归调用，在日常的js开发中，用到的真的很少。把这个问题拿出来讲，主要是想引出对arguments的一些讲解和对Y组合子这个概念的一个普及。

但既然讲都讲了，我们真的用到的话，该怎么选择呢？来，我们喜闻乐见的benchmark下： 分别测试：

// fact 
fact(10)  
// Y
(f => f(f))(fact => n => n <= 1 ? 1 : n * fact(fact)(n - 1))(10)
// Y&#39;
const fix = (f) => f(f)  
const ygen = fix(fact2)  
ygen(10)  
// callee
(function(n) {n<=1?1:n*arguments.callee(n-1)})(10)

环境：Macbook pro(2.5 GHz Intel Core i7), node-5.0.0(V8:4.6.85.28) 结果：

fact x 18,604,101 ops/sec ±2.22% (88 runs sampled)

Y x 2,799,791 ops/sec ±1.03% (87 runs sampled)

Y’ x 3,678,654 ops/sec ±1.57% (77 runs sampled)

callee x 2,632,864 ops/sec ±0.99% (81 runs sampled)

可见Y和callee的性能相差不多，因为需要临时构建函数，所以跟直接的fact递归调用有差不多一个数量级的差异,将不定点函数算出后保存下来，大概会有一倍左右的性能提升。

以上就是JavaScript 中匿名函数的递归调用的代码详细介绍的内容，更多相关内容请关注PHP中文网（www.php.cn）！