Detailed introduction to the code of recursive calling of anonymous functions in JavaScript

No matter what programming language it is, I believe that students who have written a few lines of code will be familiar with recursion. Take a simple factorial calculation as an example:

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

We can see that recursion is a call to itself within a function. So here comes the question. We know that in Javascript, there is a type of function called an anonymous function. It has no name. How to call it? Of course you can say that you can assign the anonymous function to a constant:

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

This is of course possible. But for some situations, like when a function is written without knowing that it is going to be assigned to an explicit variable, it will run into trouble. For example:

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

So is there a way that does not require giving accurate function names (function reference variable names) at all?

arguments.callee

We know that inside any function, a variable called arguments can be accessed.

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

Print out the details of this arguments variable. It can be seen that he is an instance of Arguments, and from the data structure From a technical point of view, it is an array-like object. In addition to the array-like element members and length properties, it also has a callee method. So what does this callee method do? Let's take a look at MDN

callee which is the property of the arguments object. Within the function's body, it can point to the currently executing function. This is useful when the function is anonymous, such as a function expression without a name (also called an "anonymous function").

Haha, obviously this is what we want. The next step is:

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

But there is still a problem. The MDN document clearly states that

Warning: In the strict requirements of ECMAScript fifth edition (ES5) The use of arguments.callee() is prohibited in patterns.

Oh, it turns out that it is not used in ES5’s use strict;, so in ES6, let’s change it to ES6’s arrow function and write it down. :

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

Those who have a certain ES6 foundation may have thought about it for a long time. The arrow function is a shorthand function expression, and it has the this value of the lexical scope ( That is, objects such as this, arguments, super and new.target will not be newly generated in their own scope), and they are all anonymous.

then what should we do? Hehe, we need to use a little FP thinking.

Y Combinator

There are countless articles about Y Combinator. This was written by Haskell B. Curry, a famous logician who studied under Hilbert (Haskell language is Named after him, and the Curry technique in functional programming languages ​​is also named after him) the combinatorial operator "invented" (Haskell studies combinatorial logic) seems to have a magical power, it can calculate Determine the fixed point of the lambda expression (function). This makes recursion possible.

A concept needs to be told hereFixed-point combinator:

Fixed-point combinator (English: Fixed-point combinator, or fixed-point calculation sub) is a higher-order function that computes a fixed point of other functions.

The fixed point of function f is a value x such that f(x) = x. For example, 0 and 1 are fixed points of the function f(x) = x^2 because 0^2 = 0 and 1^2 = 1. Whereas the fixed point of a first-order function (a function on simple values ​​such as integers) is a first-order value, the fixed point of a higher-order function f is another function g such that f(g) = g. Then, the fixed point operator is any function fix such that for any function f,

f(fix(f)) = fix(f). Fixed point combinators are allowed to be defined Anonymous recursive function. They can be defined using the non-recursive lambda abstraction.

The well-known (and probably simplest) fixed-point combinator in the untyped lambda calculus is called the Y combinator.

Next, we use certain calculations to derive the Y combination.

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

Having deduced this point, you already feel a shiver down your spine. Anyway, this is the first time I came into contact with the article on Cantor, Gödel, and Turing - The Eternal Golden Diagonal. When I came into contact with it, I was instantly impressed by this way of expressing programs in mathematical language.

Come on, let’s recall whether we finally got an indefinite point operator, which can find the fixed point of a higher-order functionf(Y(f)) = Y (f). Pass a function into an operator (function) and get a function that has the same function as itself but is not your own. This statement is a bit awkward, but it is full of flavor.

Okay, let’s go back to the original question, how to complete the recursion of anonymous functions? With Y combinator it is very simple:

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