js tail recursion optimization code sharing

When learning data structures and algorithms, we all know that all recursion can be optimized into stack + loop. For specific recursive functions, we generally optimize them manually.

When I was learning scala, I came into contact with the concept of tail recursion. As long as we write the recursion as tail recursion, the compiler will automatically help us optimize.
ps: Not all recursion can be rewritten as tail recursion
In js, tail recursion is usually optimized by the interpreter. However, not all JavaScript interpreters support tail recursion optimization.
For environments that do not support tail recursion optimization, we need to manually optimize the recursion into a stack + loop.
A general method is implemented here to optimize tail recursion into stack + loop.
The code is excerpted from the book "Introduction to ECMAScript" written by Ruan Yifeng.
The specific code is as follows

<span style="font-family: 微软雅黑, "Microsoft YaHei";">function tco(f) {<br/>    var value;    var active = false;    var accumulated = [];    return function accumulator() {<br/>        accumulated.push(arguments);        if(!active) {<br/>            active = true;            while(accumulated.length) {<br/>                value = f.apply(this, accumulated.shift());<br/>            }<br/>            active = false;            return value;<br/>        }<br/>    };<br/>}var sum = tco(function(x, y) {<br/>    if(y > 0) {        return sum(x + 1, y - 1);<br/>    } else {        return x;<br/>    }<br/>});let res = sum(1, 5)<br/>console.info(res);<br/></span>

This code is very exquisite!

analyze
It is known that any recursion can be written as a loop + stack.
Implement the idea of ​​converting any tail recursion into loop + stack execution without writing an implementation version for each tail recursive function.
The difficulty lies in any tail-recursive, generic implementation. Rather than targeting a certain recursive function.
Key points:

• #The data saved in the stack are exactly the parameters of the recursive function.

• For general implementation, you must rely on the original recursive function. The termination condition of the loop is exactly the end condition of the recursion.

• To push the parameters of the recursive function onto the stack without modifying the original recursive function, you must use a function instead of the recursive function being called to obtain the function input ginseng.

• The termination conditions of the recursive function are different for each recursive function, but if the recursive function is not called again, it means that the termination condition has been reached. That is, the termination condition is related to the call of the recursive function. Every time a recursive function is called, parameters are pushed onto the stack. Therefore, you can infer whether the termination condition is reached based on whether there are elements in the stack.

Related recommendations:

Detailed introduction to JavaScript call stack, tail recursion and manual optimization

Recommended courses on tail recursion

Detailed explanation on the use of tail recursion_PHP tutorial

The above is the detailed content of js tail recursion optimization code sharing. For more information, please follow other related articles on the PHP Chinese website!