JavaScript的递归之递归与循环

递归与循环

对于不同类型的需要重复计算的问题，循环和递归两种方法各有所长，能给出更直观简单的方案。另一方面，循环和递归的方法可以互相转换。任何一个循环的代码都可以用递归改写，实现相同的功能；反之亦然。在不失去其普遍性的前提下，可以把循环和递归分别用下列伪代码概括。

伪代码格式说明：循环采用while形式；变量不加定义；赋值用:=；条件表达式和执行的语句都写成函数的形式，圆括号内写上相关的值。其他语法方面，尽量接近Javascript的规范。

[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 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;
}
同样我们给出递归函数的伪代码。

[javascript]
//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;
}

//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;
}籍比较两段代码，可以看出循环和递归具有相似的构成，通过改变顺序和适当的变换，任何循环都可以用递归的方式实现。程序简单时，这种转换很容易看出。比如下面这个简单的累计求和函数：

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

//loop
function sum(num){
var result=1;
while (num>1){
result+=num;
num--;
}
return result;
}对应的递归形式:

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

//recursion
function sum2(num){
if (num>1){
return num+sum(num-1);
}else{
return 1;
}
}反之，大部分递归程序也可以直接由循环来实现。下面是求最大公约数的循环形式的函数。

[javascript]
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在内的一些浏览器已经支持该

补充：web前端 , JavaScript ,