For different types of problems that need to be repeatedly calculated, the two methods of cycle and recursive have their own strengths, which can give more intuitive and simple solutions. On the other hand, the method of circulation and recursive can be converted to each other. Any cycle of code can be rewritten recursively to achieve the same functions; vice versa. Under the premise of losing its universality, the circulation and recursive can be summarized with the following pseudo -code, respectively.
pseudo -code format description: The loop is in the form of a while; the variable is not defined; the assignment is used: =; conditional expression and execution sentences are written into functions, and related values are written in brackets. In terms of other grammar, try to get closer to the norms of JavaScript.
// While form
function loop(arguments){
// The initial value of the result
result:=initial_value;
While (Condition (variable, arguments)) {// cycle conditions may only be arguments, or to facilitate the introduction of cycle variables
// Calculate the results. The parameters include the previous results, the current circulation variable and external variables
result:=calculate(result, variable, extern_variables);
// Affect the external environment of the function, that is, modify the external variable
changeStatus(result, variable, extern_variables);
// After executing the statements in the cycle, modify the parameter or circular variable.
modify_arguments_variable(arguments, variable);
}
// Back results
return result;
}
Similarly, we give a pseudo -code for recursion functions.
function recursion(arguments){
// The following code is the structure part of the control function repeatedly called.
// Get new parameters that call this function again, which may be multiple arguments values.
// C corresponding CorITION (Variable, Arguments) and Modify_arguments_variable (ARGUMENTS, VARIABLE).
new_arguments:=conditional_get_next(arguments);
// Each group of new parameters, call the function itself.
results:=recursion(new_arguments);
// The code below is the functional part of each call running
// Calculate the result. Involved the previous results, current circulation variables and external variables.
// Result: = callculating (result, variable, extern_variables) in the cycle.
result:=calculate(arguments, extern_variables);
result:=combine(result, results);
// Affect the external environment of the function, that is, modify the external variable
changeStatus(result, arguments, extern_variables);
return result;
}
Profting two code comparison, we can see that the cycle and recursive composition have similar compositions. By changing the order and appropriate transformation, any cycle can be implemented in a recursive manner. When the program is simple, this conversion is easy to see. For example, the following simple accumulated sum of sum of summoning functions:
function sum(num){
var result=1;
while (num>1){
result+=num;
num–;
}
return result;
}
Corresponding to recursive form:
function sum2(num){
if (num>1){
return num+sum(num-1);
}else{
return 1;
}
}
Conversely, most recursive programs can also be implemented directly by cycle. Below is a function of a cycle form of the maximum number of contracts.
var temp;
if (a<b){
temp=a;
a=b;
b=temp;
}
var c=a%b;
while (c!==0){
a=b;
b=c;
c=a%b;
}
return b;
}
However, the conversion from recursion to cycle is not so easy. The new parameter part of this function is called again in the recursive pseudo -code
new_arguments:=conditional_get_next(arguments);
is more flexible than the corresponding part of the cycle. It can be recursively divided into two categories according to the number of parameter arrays (all parameters required by the function). The first category is the number of parameter arrays fixed, which can be converted into a cycle, such as the example of the Fibonacci quota and the largest division; the second category is the number of parameter arrays is uncertain -just like when traversing a picture or tree Then, each point has any adjacent points -the recursive cannot be directly converted into a cycle.
Because the cycle can only be duplicated by one dimension, recursion can traverse the two -dimensional structure. For example, in a tree, a node has both its sub -nodes and nodes of the same level. A simple one -dimensional cycle cannot be traversed in both directions.
But if we use some data structures to remember some information at the location of the location in the cycle, the second type of recursive can also be implemented with cycle.
Let’s practice the conclusions observed through an example. HTML5 defines a new method GetelementsByClassName (names) for Document and Element, and returns all Elements with a given Class value. Some browsers, including Firefox3, have supported this method. Let’s use a recursion method to give a weak function, and then rewrite it with a cycle method.
// ELEM is a htmlelement
// name is a single class name
// Return all the CLASS attributes containing ELEM include an array of Element with a 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; i<c.length; i++){
getElements(c[i]);
}
}
getElements(elem);
return list;
}
, as mentioned earlier, in order to remember the location information of the node in the cycle, we need a data structure that can implement the following methods.
push (object) // Write a object.
Objectpop () // Read a recently written object and delete it from the data structure.
ObjectGet () // Read a recently written object without changing the content of the data structure.
stack is such a data structure that is followed first. The Array object in JavaScript supports the first two methods, we can add the third method to it.
Use a circular version:
//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;
}
summarize. All cycles can be achieved with recursion; all recursion can be implemented with cycle. What kind of method is used, which is more convenient and intuitive and user’s preferences under the specific issues.
efficiency
In terms of performance, recursion is not as good as cycling. In addition to the overhead of multiple function calls, in some cases, recursion will bring unnecessary repeated calculations. Taking the recursive procedures of the Fibonacci quota as an example. At the N (n), from the N-2 item, each item is repeatedly calculated. The smaller the number, the more repeated times. The number of times to.
B(i)=1; i=n, n-1
B(i)=B(i+1)+B(i+2); i<n-1
So, B (i) forms an interesting inverse Fibona. Seeking A (n): there is:
B(i)=A(n+1-i)
From a different angle, it makes C (i) the number of additions required for A (i), and
C(i)=0; i=0, 1
C(i)=1+C(i-1)+C(i-1); i>1
Order 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 a Fibonacci series. It can also be drawn:
C(n)=A(n+1)-1
and A (N) are growth in geometric levels, which will become very amazing when N is larger when N is larger. Corresponding to this adopt a loop program, there are
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 previously given cyclic program is much faster than the recursive program.
Like the cycle in the previous section, this defect in recursive can also be made up. We only need to remember the items that have been calculated. When you find higher items, we can directly read the previous items. This technology is very common in recursion, known as “Memorization”.
Below is the recursive algorithm of seeking Fibonacci quota with storage technology.
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);
}