递归与循环
对于不同类型的需要重复计算的问题,循环和递归两种方法各有所长,能给出更直观简单的方案。另一方面,循环和递归的方法可以互相转换。任何一个循环的代码都可以用递归改写,实现相同的功能;反之亦然。在不失去其普遍性的前提下,可以把循环和递归分别用下列伪代码概括。
伪代码格式说明:循环采用while形式;变量不加定义;赋值用:=;条件表达式和执行的语句都写成函数的形式,圆括号内写上相关的值。其他语法方面,尽量接近Javascript的规范。
//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;
}
同样我们给出递归函数的伪代码。
//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;
}
籍比较两段代码,可以看出循环和递归具有相似的构成,通过改变顺序和适当的变换,任何循环都可以用递归的方式实现。程序简单时,这种转换很容易看出。比如下面这个简单的累计求和函数:
//loop
function sum(num){
var result=1;
while (num>1){
result+=num;
num--;
}
return result;
}
对应的递归形式:
//recursion
function sum2(num){
if (num>1){
return num+sum(num-1);
}else{
return 1;
}
}
反之,大部分递归程序也可以直接由循环来实现。下面是求最大公约数的循环形式的函数。
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;
}
不过,从递归到循环的转换并不是都这么容易。递归伪代码中的产生再次调用此函数的新参数部分
new_arguments:=conditional_get_next(arguments);
较之循环的对应部分更为灵活。可以按照新产生的参数组数(函数需要的所有参数为一组)将递归分为两类。第一类为参数组数固定,该递归可以转换为循环,比如斐波那契数列和最大公约数的例子;第二类为参数组数不确定——就像在遍历一个图或树的时候那样,每个点有任意个相邻的点——该递归不能直接转换为循环。
因为循环只能做一维的重复,而递归可以遍历二维的结构。比如一棵树中,一个节点既有它的子节点,也有同级的节点,简单的一维循环不能够在两个方向上遍历。
但是如果我们在循环中借助某种数据结构记住有关节点位置的一些信息,第二类递归也可以用循环实现。
我们再通过一个例子来实践上面观察得出的结论。HTML5为Document和Element新定义了一个方法getElementsByClassName(names),返回具有给定class值的所有elements。包括Firefox3在内的一些浏览器已经支持该方法。下面我们先用递归的方法给出一个功能较弱的版本,然后再用循环的方法重写它。
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;
}
如前所述,在循环中为了记住节点的位置信息,我们需要一个能实现以下方法的数据结构。
push(object) //写入一个对象。
object pop() //读出最近写入的一个对象,并将其从数据结构中删除。
object get() //读出最近写入的一个对象,不改变数据结构的内容。
堆栈正是这样一个后进先出的数据结构。Javascript中的Array对象支持前两种方法,我们在为其增加第三个方法即可。
采用循环的版本:
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);
}
(至此,几篇关于JavaScript的旧文贴完。)
分享到:
相关推荐
递归与循环 对于不同类型的需要重复计算的问题,循环和递归两种方法各有所长,能给出更直观简单的方案。另一方面,循环和递归的方法可以互相转换。任何一个循环的代码都可以用递归改写,实现相同的功能;反之亦然。...
如何提升JavaScript的运行速度(递归篇)
处理这种问题,通常我们会需要递归,来让程序自己按照一种算法去循环。在某书说写着,“递归是一种强大的编程技术”,好吧,她不仅仅属于 JavaScript。递归可以很难,也可以比较简单(总得来说还是比较难)。处理...
但是作为一个合格的程序员,我们也因该知道,递归算法相对常用的算法如普通循环等,运行效率较低。因此,应该尽量避免使用递归,除非没有更好的算法或者某种特定情况,递归更为适合的时候。在递归调用的过程当中系统...
因为这个递归函数没有停止处理或运算的出口,因此这个递归函数就演变为一个死循环。 那如何使用递归呢? 使用递归函数必须要符合两个条件: 1、 在每一次调用自己时,必须是(在某种意义上)更接近于解; 这句话怎么...
现在有一个数据,需要你渲染出对应的列表出来: var data = [ {"id":1}, {"id":2}, {"id":3}, {"id":4}, ];...我一个循环再一个循环,轻松带走你们 var data2 = [ {"id":1,children:[{"id":
主要介绍了JavaScript使用递归和循环实现阶乘的实例代码,代码简单易懂,非常不错,具有一定的参考借鉴价值,需要的朋友参考下吧
非递归的循环写法: 代码如下: 1run: function() { 2 var sum = 0; 3 for(var i=1;i<=100;i++) { 4 sum = sum + i; 5 } 6 console.log(sum); 7} 递归的写法: 代码如下: var testCase = { sum: 0, run: function...
for循环: 代码如下:for(i=start;...}递归:使用for循环做substring 代码如下:function substring(all, start, end) { for(i=start; i<=end; i++) { console.log(all[i]); } substring(“eclipse”
通过递归方法循环打印字节点。不需要层来控制。
虽然它们长度不一,但循环应付它们非常容易,也很优雅: 代码如下:[javascript] view plaincopyprint?var dumpArrayByLoop = function(a) { for (var i = 0; i < a.length; i++) { println(a[i]); } }; ...
第2章JavaScript数据类型与变量 2.1变量的标识 2.2作用域 2.3简单类型 2.4常量:有名称但不改变 2.5习题 第3章运算符和语句 3.1JavaScript语句的格式 3.2简单语句 3.3条件语句和程序流 3.4条件运算符 3.5逻辑运算符 ...
递归链的javascript实现递归链,即CR,是一个有趣的代数,对于编译器优化非常重要。 据我所知,LLVM利用此概念来实现其内部标量演化分析,从而形成了循环优化的基础。 简单来说,递归关系是一个周期性变化的数字序列...
2.6 JavaScript与旧浏览器或受限的浏览器 2.7 应知应会 练习 第3章 数据类型、字面量和变量 3.1 数据类型 3.1.1 基本数据类型 3.1.2 复合数据类型 3.2 变量 3.2.1 有效...
8-1 循环队列-原理讲解 8-2 循环队列-代码实操 8-3 任务队列-原理讲解 8-4 任务队列-代码实操 第9章 数据结构之“链表”链表是一个有序的线性数据结构,对于它而言排序和循环是最基本的两项技能,这个章节从零是...
主要介绍了JavaScript中循环遍历Array与Map的各种方法,利用的都是js入门学习中的基础知识,需要的朋友可以参考下
1.10 JavaScript与JScript、 VBScript 1.11 JavaScript与Java、Java applet 1.12 JavaScript的未来如何 1.13 本章小结 第2章 JavaScript语言入门 2.1 编程准备 2.1.1 编程术语 2.1.2 脚本执行顺序 2.1.3 大小写敏感 ...