The tail call
Definition 1.
Tail-call is a very important concept in functional programming. When a function is executed, the last step is to return the call of another function. This is called tail-call.
Note that it does not matter how the function is called. The following methods can be used:
Function call: func (...) method invocation: obj. Method: (...) call call func. Call (...) the apply call: func. Apply (...)Copy the codeAnd only the following expressions will contain trailing calls:
Conditional operators:? : logic or: | | logic and: && comma:,Copy the codeExamples in turn:
const a = x => x ? f() : g(); // f() and g() are both tails.Copy the codeconst a = () => f() || g(); Const a = () => {const fResult = f(); const fResult = f(); // not a tail callif (fResult) {
return fResult;
} else {
returng(); // tail call}} // g() is called only when f() is falseyCopy the codeconst a = () => f() && g(); Const a = () => {const fResult = f(); const fResult = f(); // not a tail callif (fResult) {
return g(); // tail call
} else {
returnfResult; }} // g() is the last call only if f() is truthyCopy the codeconst a = () => (f() , g()); Const a = () => {f(); const a = () => {f();return g();
}
Copy the code2. Tail call optimization
When a function is called, records will be stored in the Call stack, and each record is called a Call frame. Each record will be pushed to the stack when a function is called. After the function is executed, a record will be popped out successively until the call stack is emptied.
function foo () { console.log(111); }
function bar () { foo(); }
function baz () { bar(); }
baz();
Copy the code
This happens because each function does not return the call when it calls another function, so the JS engine will assume that you have not finished executing and will keep your call frame.
Baz () calls bar() and does not return the call, so it keeps its call frame in the call stack, and the call frame of bar() is generated in the call stack. Similarly, bar() calls foo(), and when foo() is executed, No other function is called, and there is no declaration of return, so return undefined by default.
When foo() is finished, it destroys its own record in the call stack, then destroys the call frames for bar() and baz(), and finally completes the process.
If the above example were modified as follows:
function foo () { console.log(111); }
function bar () { return foo(); }
function baz () { return bar(); }
baz();
Copy the codeNote here: tail-call optimization only works in strict mode.
In non-strict mode, most engines include the following two properties for developers to check the call stack:
- Func.arguments: Represents the arguments contained in the last call to func
- Caller: Refers to the function that made the most recent call to func
In tail-call optimization, these attributes are no longer useful because the relevant information can be removed as well. Therefore, strict mode disallows these properties, and tail-call optimizations only work in strict mode.
If the tail-call optimization was in effect, the flowchart would look like this:
We can clearly see that since the last call is the last operation of the function, there is no need to keep the call record of the outer function. As long as the call record of the inner function is directly replaced by the call record of the outer function, only one call frame is always kept in the call stack.
This is called tail-call optimization, if all functions are tail-call, then there is only one call frame in the call stack, which saves a lot of memory, which is the meaning of tail-call optimization.
Tail recursion
Definition 1.
Let’s start with recursion, when a function calls itself, it’s called recursion.
function foo () {
foo();
}
Copy the codeThe above operation is called recursion, but note that there is no end condition, it is dead recursion, so it will report stack overflow error, be careful when writing code to add end condition to recursion.
So what is tail recursion? Previously we saw the concept of tail-calling, when a function tail-calls itself, it is called tail-recursion.
function foo () {
return foo();
}
Copy the code2. The role
So how is tail recursion different from recursion? Let’s take a look at the following factorial example:
function factorial (num) {
if (num === 1) return 1;
return num * factorial(num - 1);
}
factorial(5); // 120
factorial(10); // 3628800
factorial(500000); // Uncaught RangeError: Maximum call stack size exceeded
Copy the codeThe above example uses recursive factorial calculation. The memory allocated by the operating system to the JS engine call stack is limited in size. If the calculated number is large enough to exceed the maximum memory range, stack overflow errors will occur.
500,000 is not the threshold here, but I used a number that was large enough to cause a stack overflow.
What if we use tail recursion to compute the factorial?
'use strict';
function factorial (num, total) {
if (num === 1) return total;
returnfactorial(num - 1, num * total); } factorial(5, 1); // 120 factorial(10, 1); // 3628800 factorial(500000, 1); // In Chrome and Firefox, a stack overflow error is reported, and tail call optimization is not performed in Safari. Factorial (500000, 1) will result in Infinity because the result is out of the JS representation range. Node-harmony_tailcalls test.js // The latest version of Node has removed the harmony_tailcalls functionCopy the codeBy tail recursion, we reduce the complexity from O(n) to O(1), which saves a lot of computing time if the data is large enough. Thus tail-call optimization is so important for recursive operations that some functional programming languages write it into the language specification.
Avoid rewriting recursive functions
Tail-recursion implementations often require rewriting the recursive function to ensure that the last step calls only itself. To do this, rewrite all intermediate variables used inside the function as arguments to the function, just like the factorial() function rewrite above.
The downside of this is that the semantics are not obvious. To compute the factorial function, why pass in an additional parameter called total? There are two ways to solve this problem:
1. Default values of ES6 parameters
'use strict';
function factorial (num, total = 1) {
if (num === 1) return total;
returnfactorial(num - 1, num * total); } factorial(5); // 120 factorial(10); / / 3628800Copy the code2. Use a semantically appropriate function to call the rewritten tail recursive function
function tailFactorial (num, total) {
if (num === 1) return total;
return tailFactorial(num - 1, num * total);
}
function factorial (num) {
returntailFactorial(num, 1); } factorial(5); // 120 factorial(10); / / 3628800Copy the codeThis is a little bit like currization of a function, but it doesn’t quite fit the concept of currization. Currization of a function converts a function that takes multiple arguments to one that takes a single argument (the first argument of the original function) and returns a new function that takes the remaining arguments and returns the result.
The concept sounds confusing, but let’s give it a taste:
// Ordinary addition functionfunction add (x, y, z) {
returnx + y + z; } add(1, 2, 3); // 6 // Rewrite as currie addition functionfunction add (x) {
return function (y) {
return function (z) {
returnx + y + z; } } } add(1)(2)(3); / / 6Copy the codeAs you can see, the Currization function uses the closure to find the variables in the parent scope and then adds them up in turn. It’s probably not clear from this example why we use Corrification, but we’ll talk about that later, but there’s a concept here.
Is the technique of transforming a function that takes multiple arguments into a function that takes a single argument (the first argument of the original function), and returning a new function that takes the remaining arguments and returns the result.
If we use the Caulization to rewrite the factorial example:
// Currization functionfunction curry (fn) {
var _fnArgLength = fn.length;
functionwrap (... args) { var _args = args; var _argLength = _args.length; // If all arguments are passed, the fn call is returnedif (_fnArgLength === _argLength) {
return fn.apply(null, args);
}
functionact (... args) { _args = _args.concat(args);if (_args.length === _fnArgLength) {
return fn.apply(null, _args);
}
return act;
}
return act;
}
returnwrap; } // tail recursive functionfunction tailFactorial (num, total) {
if (num === 1) return total;
returntailFactorial(num - 1, num * total); } // factorial = curry(tailFactorial); factorial(5)(1); // 120 factorial(10)(1); / / 3628800Copy the codeThis is in line with the concept of Currization writing method, in teacher Ruan Yifeng’s article is written like this:
function currying(fn, n) {
return function (m) {
return fn.call(this, m, n);
};
}
function tailFactorial(n, total) {
if (n === 1) return total;
return tailFactorial(n - 1, n * total);
}
const factorial = currying(tailFactorial, 1);
factorial(5) // 120
Copy the codeIn my opinion, this is not a Kerritization, because it does not rewrite the multi-parameter tailFacrotial to accept a single parameter. It is written in the same way as the following:
function factorial (num) {
return tailFactorial(num, 1);
}
function tailFactorial (num, total) {
if (num === 1) return total;
returntailFactorial(num - 1, num * total); } factorial(5); // 120 factorial(10); / / 3628800Copy the codeThe end of the
This article focuses on tail-call optimization and Currification. Note that Chrome and Firefox did not optimize tail calls when tested, and Safari did. Node advanced versions have also been removed to enable tail-call optimization via the — Harmony_tailcalls parameter.
If you have any questions, please leave comments and discuss. Please come to my blog
Welcome to follow my public number
Refer to the link
www.ruanyifeng.com/blog/2015/0… Juejin. Cn/post / 684490… Github.com/lamdu/lamdu…