Introduction to recursion and loop examples of JavaScript recursion_javascript skills

Recursion and Loop

For different types of problems that require repeated calculations, loop and recursion methods have their own advantages and can provide more intuitive and simple solutions. On the other hand, loop and recursive methods can be converted into each other. Any loop of code can be rewritten using recursion to achieve the same function; and vice versa. Without losing their generality, loops and recursions can be summarized using the following pseudocode.

Pseudocode format description: The loop adopts the while form; variables are not defined; assignment uses:=; conditional expressions and executed statements are written in the form of functions, and relevant values ​​are written in parentheses. In terms of other syntax, try to be as close to Javascript specifications as possible.

Copy code The code is as follows:

//pseudo code of a loop
// while form
function loop(arguments){
//The initial value of the result
result:=initial_value;

while(condition(variable, arguments)){//Loop condition, possible Only arguments are required, and loop variables may also be introduced for convenience
//Calculation results. Parameters include previous results, current loop variables and external variables
result:=calculate(result, variable, extern_variables);
//Affect the external environment of the function, that is, modify external variables
changeStatus(result, variable , extern_variables);
//After executing the statements in the loop body, modify the parameters or loop variables.
modify_arguments_variable(arguments, variable);
}
//Return result
return result;
}

Similarly we give the pseudo code of the recursive function.

Copy code The code is as follows:

//pseudo code of a recursion
function recursion (arguments){
//The following code is the structural part that controls the repeated calling of the function.
//Get new parameters for calling this function again, which may be multiple sets of argument values.
//Corresponds to condition(variable, arguments) and modify_arguments_variable(arguments, variable) in the loop.
new_arguments:=conditional_get_next(arguments);
//For each group of new parameters, call the function itself.
results:=recursion(new_arguments);

//The following code is the functional part that is run every time it is called.
//Calculate the results. Involves previous results, current loop variables and external variables.
//Corresponds to result:=calculate(result, variable, extern_variables) in the loop.
result:=calculate(arguments, extern_variables);
result:=combine(result, results);
//Affect the external environment of the function, that is, modify the external variables
changeStatus(result, arguments, extern_variables);
return result;
}

Comparing the two pieces of code, we can see that loops and recursions have similar compositions. By changing the order and appropriate transformations, any loop can Can be implemented recursively. This transformation is easy to see when the program is simple. For example, the following simple cumulative sum function:

Copy code The code is as follows:

// loop
function sum(num){
var result=1;
while (num>1){
result =num;
num--;
}
return result;
}

The corresponding recursive form:

Copy code Code As follows:

//recursion
function sum2(num){
if (num>1){
return num sum(num-1);
}else {
return 1;
}
}

Conversely, most recursive programs can also be implemented directly by loops. The following is a function in the form of a loop that finds the greatest common divisor.

Copy code The code is as follows:

function gcd2(a, b){
var temp;
if (atemp=a;
a=b;
b=temp;
}
var c=a%b;
while (c!==0){
a=b;
b=c;
c=a%b;
}
return b;
}

However, the transition from recursion to looping is not always easy. The part in the recursive pseudocode that generates new arguments for calling this function again

new_arguments:=conditional_get_next(arguments);

is more flexible than the corresponding part of the loop. Recursion can be divided into two categories according to the number of newly generated parameter groups (all parameters required by the function are one group). The first type is when the number of parameter groups is fixed, and the recursion can be converted into a loop, such as the Fibonacci sequence and the greatest common divisor example; the second type is when the number of parameter groups is uncertain - just like when traversing a graph or tree That way, each point has any number of adjacent points - this recursion cannot be directly converted into a loop.

Because loops can only do one-dimensional repetitions, while recursion can traverse two-dimensional structures. For example, in a tree, a node has both its child nodes and nodes at the same level. A simple one-dimensional loop cannot traverse in both directions.

But the second type of recursion can also be implemented with loops if we remember some information about the node position with the help of some data structure.

Let’s use another example to practice the conclusion drawn from the above observation. HTML5 defines a new method getElementsByClassName(names) for Document and Element, which returns all elements with a given class value. Some browsers, including Firefox 3, already support this method. Below we first use a recursive method to give a weaker version, and then rewrite it using a loop method.

Copy code The code is as follows:

var getElementsByClass={};

//elem is an HTMLElement
//name is a single class name
//returns an array containing elements with all class attributes under elem containing the given name
getElementsByClass.recursion1=function (elem, name){
var list=[];
function getElements(el){
if (el.className.split(' ').indexOf(name)>-1){
list.push( el);
}
for (var i=0, c=el.children; igetElements(c[i]);
}
}
getElements(elem);
return list;
}

As mentioned before, in order to remember the position information of the node in the loop, we need a function that can implement the following The data structure of the method.

push(object) //Write an object.

objectpop() //Read the most recently written object and delete it from the data structure.

objectget() //Read the most recently written object without changing the contents of the data structure.

The stack is exactly such a last-in-first-out data structure. The Array object in Javascript supports the first two methods, and we can add a third method to it.

The looped version:

Copy the code The code is as follows:

getElementsByClass .loop1 = function(elem, name){
//use a js array as the basis of a needed stack
var stack = [];
stack.get = function(){
return stack[stack.length - 1];
}

var list = [];
//the business logic part. put the eligible element to the list.
function testElem(el ){
if (el.className.split(' ').indexOf(name) > -1) {
list.push(el);
}
}
// check the root element
testElem(elem);
//initialize the stack
stack.push({
pointer: elem,
num: 0
});
var parent, num, el;
while (true) {
parent = stack.get();
el = parent.pointer.children[parent.num];
if (el) { //enter a deeper layer of the tree
testElem(el);
stack.push({
pointer: el,
num: 0
});
}
else {//return to the upper layer
if (stack.pop().pointer === elem) {
break;
}
else {
stack.get() .num = 1;
}
}
}

return list;
}

To sum it up. All loops can be implemented using recursion; all recursion can be implemented using loops. Which method is used depends on which idea is more convenient and intuitive for specific problems and the user's preferences.

Efficiency

In terms of performance, recursion has no advantage over loops. In addition to the overhead of multiple function calls, recursion can also lead to unnecessary repeated calculations in some cases. Take, for example, a recursive program that calculates the Fibonacci sequence. When finding the nth item A(n), starting from the n-2nd item, each item is calculated repeatedly. The smaller the number of items, the more times it is repeated. Let B(i) be the number of times the i-th item is calculated, then there is

B(i)=1; i=n, ​​n-1

B(i)=B(i 1) B(i 2); i
In this way, B(i) forms an interesting inverse Fibonacci sequence. When finding A(n):

B(i)=A(n 1-i)

Looking at it from another perspective, let C(i) be when finding A(i) The number of additions required is:

C(i)=0; i=0, 1

C(i)=1 C(i-1) C(i-1) ; i>1

Let D(i)=C(i) 1, there is

D(i)=1; i=0, 1

D(i )=D(i-1) D(i-1)

So D(i) forms another Fibonacci sequence. And it can be concluded:

C(n)=A(n 1)-1

And A(n) grows in a geometric series. This redundant repetition increases when n is smaller. It becomes quite astonishing when it gets bigger. The corresponding program using loops has

B(n)=1; n is any value

C(n)=0; n=0, 1

C(n)=n-1; n>1

Therefore, when n is large, the program using loops given above will be much faster than the program using recursion.

Like the loop in the previous section, this flaw in recursion can also be made up for. We only need to remember the terms that have been calculated, and when finding higher terms, we can directly read the previous terms. This technique is common in recursion and is called memorization.

The following is a recursive algorithm for finding the Fibonacci sequence using storage technology.

Copy code The code is as follows:

//recursion with memorization
function fibonacci4(n ){
var memory = []; //used to store each calculated item
function calc(n){
var result, p, q;
if (n < 2) {
memory[n] = n;
return n;
}
else {
p = memory[n - 1] ? memory[n - 1] : calc(n - 1);
q = memory[n - 2] ? memory[n - 2] : calc(n - 2);
result = p q;
memory[n] = result;
return result;
}
}
return calc(n);
}