Recursion and loop examples of JavaScript recursion

For different types of problems that require repeated calculations, loop and recursion methods have their own advantages and can provide a more intuitive and simple solution. The following is a detailed introduction to JavaScript's recursion and loop for those who are interested. You can learn about

Recursion and loop

For different types of problems that require repeated calculations, loop and recursion methods have their own advantages and can give a more intuitive Simple solution. 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.

The code is as follows:

//pseudo code of a loop 
//while形式 
function loop(arguments){ 
//结果的初始值 
result:=initial_value; 
while(condition(variable, arguments)){//循环条件，可能只需arguments，也可能为了方便引入循环变量 
//计算结果。参数包括之前的结果、当前循环变量和外部变量 
result:=calculate(result, variable, extern_variables); 
//影响函数的外部环境，即修改外部变量 
changeStatus(result, variable, extern_variables); 
//执行完循环体中的语句后，修改参数或循环变量。 
modify_arguments_variable(arguments, variable); 
} 
//返回结果 
return result; 
}

Similarly we give the pseudo code of the recursive function.

The code is as follows:

//pseudo code of a recursion 
function recursion(arguments){ 
//以下代码为控制函数重复调用的结构部分。 
//获得再次调用此函数的新的参数，可能为多组arguments值。 
//对应于循环中的condition(variable, arguments)和modify_arguments_variable(arguments, variable)。 
new_arguments:=conditional_get_next(arguments); 
//对新参数的每一组，调用函数自身。 
results:=recursion(new_arguments); 
//以下的代码为每次调用都运行的功能部分 
//计算结果。涉及到之前的结果、当前循环变量和外部变量。 
//对应于循环中的result:=calculate(result, variable, extern_variables)。 
result:=calculate(arguments, extern_variables); 
result:=combine(result, results); 
//影响函数的外部环境，即修改外部变量 
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 making appropriate transformations, any loop can use recursion. way to achieve. This transformation is easy to see when the program is simple. For example, the following simple cumulative sum function:

The code is as follows:

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

The corresponding recursive form:
The code is 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.

The code is as follows:

function gcd2(a, b){ 
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 loop is not always so 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 if we use some data structure to remember some information about the node position in the loop, the second type of recursion can also be implemented with a loop.

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.

The code is as follows:

var getElementsByClass={}; 
//elem为一个HTMLElement 
//name为单个class名 
//返回包含elem下所有class属性包含给定名称的element的数组 
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 before, in order to remember the position information of the node in the loop, we need a data structure that can implement the following 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.

Using the loop version:

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; 
}

归纳起来。所有循环都可以用递归实现；所有递归都可以用循环实现。采用哪种方法，由具体问题下哪种思路更方便直观和使用者的喜好决定。

效率

性能方面，递归不比循环有优势。除了多次函数调用的开销，在某些情况下，递归还会带来不必要的重复计算。以计算斐波那契数列的递归程序为例。求第n项A(n)时，从第n-2项起，每一项都被重复计算。项数越小，重复的次数越多。令B(i)为第i项被计算的次数，则有

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

B(i)=B(i+1)+B(i+2); i
这样，B(i)形成了一个有趣的逆的斐波那契数列。求A(n)时有：

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

换一个角度来看，令C(i)为求A(i)时需要的加法的次数，则有

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

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

令D(i)=C(i)+1，有

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

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

所以D(i)又形成一个斐波那契数列。并可因此得出：

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

而A(n)是以几何级数增长，这种多余的重复在n较大时会变得十分惊人。与之相对应的采用循环的程序，有

B(n)=1; n为任意值

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

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

因而当n较大时，前面给出的采用循环的程序会比采用递归的程序快很多。

如上一节中的循环一样，递归中的这个缺陷也是可以弥补的。我们只需要记住已经计算出来的项，求较高项时，就可以直接读取以前的项。这种技术在递归中很普遍，被称为“存储”(memorization)。

下面是采用存储技术的求斐波那契数列的递归算法。

代码如下:

//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); 
}

更多JavaScript的递归之递归与循环示例介绍相关文章请关注PHP中文网！