Detaillierte Einführung in den Code des rekursiven Aufrufs anonymer Funktionen in JavaScript

Egal um welche Programmiersprache es sich handelt, ich glaube, dass Schüler, die ein paar Codezeilen geschrieben haben, mit Rekursion vertraut sind. Nehmen Sie als Beispiel eine einfache faktorielle Berechnung:

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

Wir können sehen, dass Rekursion ein Aufruf an sich selbst innerhalb einer Funktion ist. Hier stellt sich die Frage. Wir wissen, dass es in Javascript eine Art Funktion gibt, die als anonyme Funktion bezeichnet wird. Natürlich kann man sagen, dass man die anonyme Funktion einer Konstante zuweisen kann:

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

Das ist natürlich möglich. Aber in manchen Situationen, etwa wenn eine Funktion geschrieben wird, ohne zu wissen, dass sie einer expliziten Variablen zugewiesen wird, kann es zu Problemen kommen. Zum Beispiel:

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

Gibt es also eine Möglichkeit, die die Angabe genauer Funktionsnamen (Funktionsreferenzvariablennamen) überhaupt nicht erfordert?

arguments.callee

Wir wissen, dass in jedem function auf eine Variable namens arguments zugegriffen werden kann.

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

gibt die Details dieser arguments-Variablen aus. Es ist ersichtlich, dass es sich um eine Instanz von Arguments handelt, und aus Sicht der Datenstruktur ist dies der Fall. es ist ein Array-ähnliches. Zusätzlich zu den Array-ähnlichen Elementmitgliedern und length-Attributen verfügt es auch über eine callee-Methode. Was bewirkt diese callee-Methode? Werfen wir einen Blick auf MDN

callee, das Attribut des arguments-Objekts. Innerhalb des Funktionskörpers kann es auf die aktuell ausgeführte Funktion verweisen. Dies ist nützlich, wenn die Funktion anonym ist, beispielsweise ein Funktionsausdruck ohne Namen (auch „anonyme Funktion“ genannt).

Haha, das ist natürlich das, was wir wollen. Der nächste Schritt ist:

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

Aber es gibt noch ein anderes Problem. Das MDN-Dokument besagt eindeutig:

警告: Im strengen Modus der fünften Ausgabe von ECMAScript (ES5). Die Verwendung von arguments.callee() ist verboten.

Oh, es stellt sich heraus, dass es in ES5s use strict; nicht verfügbar ist, also wechseln wir in ES6 zu ES6s arrow function und schreiben es auf:

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

ist verfügbar Für diejenigen unter Ihnen, die mit ES6 vertraut sind, möchten Sie dies möglicherweise schon seit langem sagen: Die Pfeilfunktion ist ein Kurzfunktionsausdruck und hat den Wert this des lexikalischen Bereichs (d. h.). generiert kein neues this in seinem eigenen Bereich). , arguments, super und new.target und andere Objekte) und sind alle anonym.

Was sollen wir tun? Hehe, wir müssen ein wenig FP-Denken verwenden.

Y-Kombinator

Es gibt unzählige Artikel über Y Combinator Dies wurde von Haskell B. Curry geschrieben, einem berühmten Logiker, der bei Hilbert studierte (die Haskell-Sprache ist nach ihm benannt). Die Curry-Technik in funktionalen Programmiersprachen ist ebenfalls nach ihm benannt. Der kombinatorische Operator (Haskell untersucht die kombinatorische Logik) scheint eine magische Kraft zu haben. Er kann einen bestimmten Lambda-Ausdruck (Funktion) berechnen. Dadurch ist eine Rekursion möglich.

Hier gibt es ein Konzept, das informiert werden muss 不动点组合子:

Ein Festkomma-Kombinator (englisch: Fixed-Point Combinator oder Festkomma-Operator) ist ein Methode zur Berechnung anderer Funktionen Funktionen höherer Ordnung an festen Punkten.

Der Fixpunkt der Funktion f ist ein Wert x mit f(x) = x. Beispielsweise sind 0 und 1 Fixpunkte der Funktion f(x) = x^2, da 0^2 = 0 und 1^2 = 1. Während der Fixpunkt einer Funktion erster Ordnung (eine Funktion auf einfachen Werten wie ganzen Zahlen) ein Wert erster Ordnung ist, ist der Fixpunkt einer Funktion höherer Ordnung f eine andere Funktion g mit f(g) = g. Dann ist ein Festkommaoperator eine beliebige Funktionsfixierung, sodass

f(fix(f)) = fix(f) für jede Funktion f die Definition anonymer rekursiver Funktionen ermöglicht. Sie können mithilfe der nicht rekursiven Lambda-Abstraktion definiert werden.

Der bekannte (und wahrscheinlich einfachste) Festkomma-Kombinator in der untypisierten Lambda-Rechnung wird Y-Kombinator genannt.

Als nächstes verwenden wir bestimmte Berechnungen, um die Y-Kombination abzuleiten.

// 首先我们定义这样一个可以用作求阶乘的递归函数
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

Nachdem ich es hier herausgefunden habe, läuft einem schon ein Schauer über den Rücken. Mein erster Kontakt mit dem Autor war jedenfalls Cantor, Gödel, Turing – die ewige goldene Diagonale In diesem Artikel war ich sofort beeindruckt von dieser Art, Programme in mathematischer Sprache auszudrücken.

Kommen wir und erinnern wir uns, ob wir endlich einen unbestimmten Punktoperator haben, der den Fixpunkt einer Funktion höherer Ordnung finden kann f(Y(f)) = Y(f). Übergeben Sie eine Funktion an einen Operator (Funktion) und erhalten Sie eine Funktion, die dieselbe Funktion wie sie selbst hat, aber nicht Ihre eigene ist. Diese Aussage ist etwas umständlich, aber voller Geschmack.

Okay, kehren wir zur ursprünglichen Frage zurück: Wie vervollständigt man die Rekursion anonymer Funktionen? Ganz einfach geht das mit der Y-Kombination:

/*求不动点*/
(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）！