ES6 contains special requirements in a performance area. This is related to a specific optimization form involving function calls: Tail Call Optimization (TCO). Simply put, a tail call is a function call that appears at the end of another function. After this call is over, there is nothing else to do (except for possible return result values)
What is the call
For example, the following is a non-recursive tail call:
function foo(x) {
return x
}
// Tail callfunction bar(y) {
return foo(y + 1)
}
// Non-tailed callfunction baz() {
return 1 + bar(40)
}
baz() // Output 42
Note: foo(y+1) is the tail call in bar(...) because after foo(...) is completed, bar(...) is also completed, and only the result of the foo(...) call needs to be returned. However, bar(40) is not a tail call, because after it is finished, its result needs to be added 1 to be returned by baz() .
In JavaScript, calling a new function requires an additional reserved piece of content to manage the call stack and become a stack frame. Therefore, the previous code generally needs to keep a stack frame for each baz() , bar(...) , foo(...).
However, if the TCO-enabled engine can realize that the foo(y+1) call is at the tail, which means that bar(...) is basically done, then when foo(...) is called, it does not need to create a new frame stack, but can reuse the existing bar(...) frame stack. This not only speeds up, but also saves memory.
What is tail recursion
In computer science, a tail call refers to the situation where the last action in a function is a function call: that is, the return value of this call is directly returned by the current function. In this case, the call position is called the tail position. If this function calls itself at the tail position (or other functions that call itself, etc.), this situation is called tail recursion, which is a special case of recursion. Tail calls are not necessarily recursive calls, but tail recursive is particularly useful and easier to implement.
The significance of TCO
When the program is running, the computer will allocate a certain amount of memory space to the application; the application will allocate the obtained memory space itself, part of which is used to record the operation of each function being called in the program. This is the function call stack. A regular function call always adds a new stack frame (stack frame, also translated as "stack frame" or simply "frame") to the top of the call stack. This process is called "stack" or "stack press" (that means pushing a new frame on the top of the stack). When the number of calling layers of a function is very large, the call stack will consume a lot of memory, and may even burst the memory space (stack overflow), causing serious lag or unexpected crashes of the program. The call stack of tail calls is particularly easy to optimize, which can reduce the use of memory space and improve the running speed. Among them, the optimization effect of tail recursion is the most obvious, especially in cases where recursion algorithms are very complex.
In simple code snippets, this kind of optimization is nothing, but when dealing with recursion, this solves the big problem, especially if recursion can lead to hundreds of stack frames. With TCO, the engine can execute all such calls with the same stack frame!
Recursion is a complex topic in JavaScript. Because if there is no TCO, the engine needs to implement a random limit to define the depth of the recursive stack, and it must be stopped when it reaches it to prevent memory exhaustion. With TCO, tail-called recursive functions can essentially run arbitrarily because there is no need to use extra memory, and there is no memory overflow problem.
The following is a typical factorial function that uses tail recursion:
// Implement with loopsfunction factorial(n) {
if (n<2) return 1
var res = 1
for (var i = n; i > 1; i--) {
res *= i
}
return res
}
// Implement with tail recursionfunction factorial(n) {
function fact(n, res) {
if (n < 2) return res
return fact(n-1, n*res)
}
return fact(n, 1)
}
factorial(5) // Output 120
Note: TCO is only used in cases where there are actual tail calls. If you write a function without tail calls, then the performance will still return to the situation of ordinary frame stack allocation, and the engine's restrictions on such recursive call stacks are still valid.
Summarize
Generally speaking, tail call elimination is optional, available or not. However, in functional programming languages, language standards usually require the compiler or running platform to implement tail call elimination. This allows programmers to replace loops with recursion without losing performance. One reason why ES6 requires the engine to implement TCO instead of leaving it to the engine to decide freely is that the lack of TCO will cause some JavaScript algorithms to reduce the probability of recursive implementation because of fear of call stack restrictions.
If the engine lacks TCO in all cases just reduces performance, it won't be what ES6 requires. However, since the lack of TCO can indeed make some programs unimplemented, it becomes an important language feature rather than a hidden implementation detail. ES6 ensures that JavaScript developers can rely on this optimization in all ES6+-compliant browsers from now on. This is a win for JavaScript performance.
References
《JavaScript you don't know - Medium Volume》
This is the end of this article about the use of ES6 tail call optimization. For more related ES6 tail call optimization content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!