Recursive Call of Anonymous Functions in JavaScript

No matter what programming language, I believe that students who have written a few lines of code are no strangers to recursion. Take a simple factorial calculation as an example:

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

As we can see, recursion is a call to itself from within a function. Then the question comes. We know that in Javascript, there is a class of functions called anonymous functions without names. How can we call them? Of course, you can say that you can assign an anonymous function to a constant:

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

This is certainly possible. But for one example, when a function is written without knowing that it is going to assign a value to an explicit variable, it will encounter trouble. Such as:

(function(f){
  f(10);
})(function(n){
   if (n <= 1) {
    return 1;
  } else {
    return n * factorial(n-1);// Too dependent on context variable names 
  }
})
//Uncaught ReferenceError: factorial is not defined( … )

So is there a way to give an exact function name (function reference variable name) that doesn't need it at all?

arguments.callee

We know that within any function, we can access a variable called arguments.

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

Screenshot 2016-09-18 10.53. 58 pm

Print out the details of this arguments variable, and you can see that it is an instance of Arguments, and in terms of data structure, it is a class array. In addition to the element members of the class array and the length attribute, he also has an callee method. So what does this callee method do? Let's take a look at MDN

callee is a property of an arguments object. Within the function body of the function, 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 known as 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 another problem, which is clearly pointed out in MDN documentation

Warning: arguments. callee () is prohibited in the strict mode of ECMAScript version 5 (ES 5).

Alas, the original use strict in ES5; If you don't use it in ES6, let's change it to arrow function of ES6:

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

Students who have a definite ES6 foundation probably want to say for a long time that the arrow function is a short form of function expression, and it has the value of this in lexical scope (that is, it will not generate new objects such as this, arguments, super and new. target in its own scope), and they are all anonymous.

What can I do? Hey hey, we need to use the idea of 1 point FP.

Y combinator

There are countless articles about Y Combinator. This combination operator (Haskell studies combinational logic (combinatory logic), which was "invented" by the famous logician Haskell B. Curry named after him, and the Curry technique in functional programming language is also named after him, seems to have a magical magic power, which can calculate the fixed point of a given lambda expression (function). Which makes recursion possible.

Here, we need to tell a concept fixed point combinator:

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

The fixed point of the function f is a value x such that f (x) = x. For example, 0 and 1 are fixed points for the function f (x) = x ^ 2, because 0 ^ 2 = 0 and 1 ^ 2 = 1. Given that the fixed point of a first-order function (a function on a simple value such as an integer) 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 so that for any function f

f (fix (f) = fix (f). Fixed point combiners allow anonymous recursive functions to be defined. They can be defined in a non-recursive lambda abstraction.

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

Next, we push the next Y combinator through the calculus of 1.

//  First of all, we define this 1 A recursive function that can be used to find factorial 
const fact = (n) => n<=1?1:n*fact(n-1) 
console.log(fact(5)) //120
//  Since this function is not given a name, we first give this recursive method 1 A man called self Code name of 
//  The first is 1 Object that accepts this recursive function as an argument 1 High order function 
const fact_gen = (self) => (n) => n<=1?1:n*self(n-1) 
console.log(fact_gen(fact)(5)) //120
//  We are putting recursive methods and parameters n Is passed into the recursive method, resulting in this 1 Functions 
const fact1 = (self, n) => n<=1?1:n*self(self, n-1) 
console.log(fact1(fact1, 5)) //120
//  We will fact1  Ke Lihua, obtained fact2
const fact2 = (self) => (n) => n<=1?1:n*self(self)(n-1) 
console.log(fact2(fact2)(5)) //120
//  Surprise happened, if we will self(self) See as 1 A whole 
//  Pass in as a parameter 1 A new function : (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  And 1 The problem is that this newly extracted function is context-sensitive 
//  He relies on the above n,  So we will n As a new parameter 
//  To reconstruct this 1 Functions : (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))
//  It's obvious fact4 In (g) => (m) => m<=1?1:m*g(m-1)  Is  fact_gen
//  This is very interesting, this fact_gen Context free ,  Can be passed in as a parameter 
const weirdFunc = (func_gen) => (self) => (n) => func_gen(self(self))(n) 
console.log(weirdFunc(fact_gen)(weirdFunc(fact_gen))(5)) //120
//  At this point, we get 1 Species Y The form of combinator 
const Y_ = (gen) => (f) => (n)=> gen(f(f))(n)
//  Structure 1 Factorial recursion is also very easy It's over 
const factorial = Y_(fact_gen) 
console.log(factorial(factorial)(5)) //120
//  But this one above factorial It's not what we want 
//  It's just 1 Species fact2,fact3,fact4 Form of 
//  We definitely hope that the call to this function is factorial(5)
//  No problem, we just need to define 1 A  f' = 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

Derived from this, have you already felt your back cool for a while? Anyway, when I first came into contact with Cantor, Godel and Turing-Eternal Golden Diagonal, the whole person was instantly impressed by this way of expressing programs in mathematical language.

Now, let's recall whether we ended up with an indefinite point operator, which can find the fixed point f (Y (f)) = Y (f) of a higher order function. Pass a function into an operator (function), and get a function that is similar to its own function but not its own. This statement is somewhat awkward, but it tastes 10 feet.

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

(f => f(f))
(fact => n => n <= 1 ? 1 : n * fact(fact)(n - 1)) 
(5)
// 120

I have seen some sayings that "the most frustrating thing is that when you deduce it (Y combinator), you can't tell what it really wants by looking at it once", but I just think this is the charm of functional programming and mathematics. The simplified and elegant formula hides a complicated and interesting derivation process.

Summarize

Pragmatically speaking, recursive calls to anonymous functions are rarely used in daily js development. Taking this question out, I mainly want to lead to some explanations of arguments and a popularization of the concept of Y combinator.

But now that we have said everything, how should we choose if we really use it? Come, we like to see under benchmark: Test separately:

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

Environment: Macbook pro (2.5 GHz Intel Core i7), node-5. 0. 0 (V8: 4.6. 85.28) Results:

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)

It can be seen that the performance of Y and callee is similar, because temporary builders are needed, so it is almost one order of magnitude different from direct recursive calls of fact. If the fixed-point functions are calculated and saved, the performance will be improved by about one time.