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<n-1
这样，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);
}
您可能感兴趣的文章: