Introduction détaillée au code d'appel récursif de fonctions anonymes en JavaScript

Peu importe de quel langage de programmation il s'agit, je pense que les étudiants qui ont écrit quelques lignes de code seront familiers avec la récursivité. Prenons comme exemple un simple calcul factoriel :

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

On voit que la récursivité est un appel à elle-même au sein d'une fonction. Voici donc la question. Nous savons qu’en Javascript, il existe un type de fonction appelée fonction anonyme. Comment l’appeler ? Bien sûr on peut dire que l'on peut affecter la fonction anonyme à une constante :

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

C'est bien sûr possible. Mais dans certaines situations, comme lorsqu'une fonction est écrite sans savoir qu'elle va être affectée à une variable explicite, elle rencontrera des problèmes. Par exemple :

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

Existe-t-il donc un moyen qui ne nécessite pas du tout de donner des noms de fonctions précis (noms de variables de référence de fonction) ?

arguments.callee

Nous savons qu'à l'intérieur de tout function, une variable appelée arguments est accessible.

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

imprime les détails de cette variable arguments On peut voir qu'il s'agit d'une instance de Arguments, et du point de vue de la structure des données, c'est un type de tableau. En plus des membres d'éléments de type tableau et des attributs length, il dispose également d'une méthode callee. Alors à quoi sert cette callee méthode ? Jetons un coup d'œil à MDN

callee qui est l'attribut de l'objet arguments. Dans le corps de la fonction, il peut pointer vers la fonction en cours d'exécution. Ceci est utile lorsque la fonction est anonyme, comme une expression de fonction sans nom (également appelée « fonction anonyme »).

Haha, c’est évidemment ce que nous voulons. L'étape suivante est :

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

Mais il y a un autre problème. Le document MDN indique clairement que

警告 : Dans le mode strict de la cinquième édition d'ECMAScript (ES5) L'utilisation de arguments.callee() est interdite.

Oh, il s'avère que ce n'est pas disponible dans les ES5 use strict;, donc dans ES6, passons aux ES6 arrow function et notons-le :

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

est disponible Pour ceux d'entre vous qui connaissent ES6, vous avez peut-être eu envie de le dire il y a longtemps. La fonction flèche est une expression de fonction abrégée, et elle a la valeur this de la portée lexicale (c'est-à-dire qu'elle est disponible). ne générera pas de nouveau this dans sa propre portée). , arguments, super et new.target et autres objets), et sont tous anonymes.

Que devons-nous faire ? Héhé, nous devons utiliser un peu de réflexion FP.

Combinateur Y

Il existe d'innombrables articles sur Y Combinator Ceci a été écrit par Haskell B. Curry, un célèbre logicien qui a étudié sous Hilbert (la langue Haskell porte son nom). La technique du curry dans les langages de programmation fonctionnels porte également son nom. L'opérateur combinatoire « inventé » (Haskell étudie la logique combinatoire) semble avoir un pouvoir magique. Il peut calculer un point fixe d'expression lambda (fonction). Cela rend la récursivité possible.

Il y a un concept qui doit être informé ici 不动点组合子 :

Un combinateur à virgule fixe (anglais : combinateur à virgule fixe ou opérateur à virgule fixe) est un méthode de calcul d'autres fonctions Fonctions d'ordre supérieur en points fixes.

Le point fixe de la fonction f est une valeur x telle que f(x) = x. Par exemple, 0 et 1 sont des points fixes de la fonction f(x) = x^2 car 0^2 = 0 et 1^2 = 1. Alors que le point fixe d'une fonction du premier ordre (une fonction sur des valeurs simples comme des entiers) est une valeur du premier ordre, le point fixe d'une fonction d'ordre supérieur f est une autre fonction g telle que f(g) = g. Ensuite, un opérateur à virgule fixe est n'importe quelle fonction fixe telle que pour toute fonction f,

f(fix(f)) = fix(f) Les combinateurs à virgule fixe permettent la définition de fonctions récursives anonymes. Ils peuvent être définis à l'aide de l'abstraction lambda non récursive

Le combinateur à virgule fixe bien connu (et probablement le plus simple) dans le calcul lambda non typé est appelé le combinateur Y.

Ensuite, nous utilisons certains calculs pour dériver la combinatoire 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

Après l'avoir déduit ici, vous ressentez déjà un frisson dans le dos. Quoi qu'il en soit, mon premier contact avec l'auteur a été Cantor, Gödel, Turing - l'éternelle diagonale dorée. article, j'ai été immédiatement impressionné par cette façon d'exprimer les programmes en langage mathématique.

Voyons, rappelons si nous avons enfin un opérateur de point indéfini, qui peut trouver le point fixe d'une fonction d'ordre supérieur f(Y(f)) = Y(f). Passez une fonction dans un opérateur (fonction) et obtenez une fonction qui a la même fonction qu'elle mais qui n'est pas la vôtre. Cette instruction est un peu gênante, mais elle est pleine de saveur.

Bon, revenons à la question initiale, comment compléter la récursion des fonctions anonymes ? C'est très simple avec la combinaison 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）！