JavaScript的递归之更多例子

更多例子

第二个递归的例子是求两个自然数的最大公约数（有没有回到令人怀念的中学时代）。下面的程序用的是经典的辗转相除法。

[javascript]
//greatest common divisor  
//假定a、b都是正整数  
function gcd(a, b){ 
    if (a < b) return gcd(b, a);//ensure a >= b  
    var c = a % b; 
    if (c === 0) 
        return b; 
    else 
        return gcd(b, c); 
} 

//greatest common divisor
//假定a、b都是正整数
function gcd(a, b){
 if (a < b) return gcd(b, a);//ensure a >= b
 var c = a % b;
 if (c === 0)
  return b;
 else
  return gcd(b, c);
}
除了上面这些条件或者解法可以转化为数学的递归定义的计算，递归方法还适用于其所涉及的数据结构即是以递归形式定义的问题，比如链表、图、树等等。

现在我们来看一个迷宫的例子。迷宫可以抽象成一副数学上的图，每个岔路口是一个点，其间的路是边。两个特殊的点，分别被定义成入口和出口。

立即学习“Java免费学习笔记（深入）”；

下面是用Javascript定义的点和图。每个点包含一个id作为编号和标志，相邻的点被保存在一个数组中。图有一个添加点的方法，和一个更方便使用的直接添加点的id的方法；还有一个添加边的方法。

[javascript]
//define a vertex  
function Vertex(id){ 
    var stem={}; 
    stem.id=id; 
    stem.adjacent=[]; 
    return stem; 
}  
//define a graph  
function Graph(){ 
    var stem={}, vertices={}; 
    //add vertices to the graph  
    function add(vertex){ 
        if (vertex instanceof Array){ 
            for (var i=0, v=vertex; i<v.length; i++){ 
                vertices[v[i].id]=v[i]; 
            } 
        } 
        vertices[vertex.id]=vertex; 
    } 
    //create vertices from ids and add them to the graph  
    function addIds(ids){ 
        var id; 
        for (var i=0; i<ids.length; i++){ 
            id=ids[i]; 
            vertices[id]=Vertex(id); 
        }    
    } 
    //create an edge between two vertices  
    function connect(i1, i2){ 
        var v1=vertices[i1], v2=vertices[i2]; 
        if (v1 && v2){ 
            v1.adjacent.push(v2); 
            v2.adjacent.push(v1); 
        } 
    } 
    stem.vertices=vertices; 
    stem.add=add; 
    stem.addIds=addIds; 
    stem.connect=connect; 
    return stem; 
} 

//define a vertex
function Vertex(id){
 var stem={};
 stem.id=id;
 stem.adjacent=[];
 return stem;
}
//define a graph
function Graph(){
 var stem={}, vertices={};
 //add vertices to the graph
 function add(vertex){
  if (vertex instanceof Array){
   for (var i=0, v=vertex; i<v.length; i++){
    vertices[v[i].id]=v[i];
   }
  }
  vertices[vertex.id]=vertex;
 }
 //create vertices from ids and add them to the graph
 function addIds(ids){
  var id;
  for (var i=0; i<ids.length; i++){
   id=ids[i];
   vertices[id]=Vertex(id);
  } 
 }
 //create an edge between two vertices
 function connect(i1, i2){
  var v1=vertices[i1], v2=vertices[i2];
  if (v1 && v2){
   v1.adjacent.push(v2);
   v2.adjacent.push(v1);
  }
 }
 stem.vertices=vertices;
 stem.add=add;
 stem.addIds=addIds;
 stem.connect=connect;
 return stem;
}我们走出迷宫的思路是从入口开始，遍历每个点所有相邻的点，直到找到出口。因为图可能会包含环，也就是在迷宫中会出现兜圈子的情况，所以程序中记录每个到过的点，如果再次遇上，则返回上一个点。如果遇到出口，则退出整个遍历，返回到入口，途中记录经过的每个点，并最终写出从入口到出口的路线。这不是一个最优的办法，得到的结果未必是最短的路线，但是只要入口和出口之间是连通的，就一定可以找到一条路线。

[javascript]
//try to walk out of the maze and print the result  
function walkOut(entry, exit){ 
    var visited = [], path = []; 
     
    function walk(vertex){ 
        if (vertex === exit) {//find the exit  
            path.push(vertex); 
            return true; 
        } 
        if (visited.indexOf(vertex) > -1) {//the vertex was visited  
            return false; 
        } 
        visited.push(vertex);//remember each vertex  
        var connected = vertex.adjacent; 
        var length = connected.length; 
        if (length === 0) {//the vertex is isolated  
            return false; 
        } 
        for (var i = 0; i < length; i++) { 
            if (walk(connected[i])) {//try each adjacent vertex  
                path.push(vertex); 
                return true; 
            } 
        } 
    } 
     
    function printPath(){ 
    var footprint = ''; 
    var length = path.length; 
    for (var i = length - 1; i > -1; i--) { 
        footprint += path[i].id; 
        footprint += i === 0 ? '' : ' > '; 
    } 
    print(footprint); 
} 
 
    if (walk(entry)) { 
        printPath(); 
    } 
    else { 
        print('出不去！'); 
    } 
} 

//try to walk out of the maze and print the result
function walkOut(entry, exit){
    var visited = [], path = [];
   
    function walk(vertex){
        if (vertex === exit) {//find the exit
            path.push(vertex);
            return true;
        }
        if (visited.indexOf(vertex) > -1) {//the vertex was visited
            return false;
        }
        visited.push(vertex);//remember each vertex
        var connected = vertex.adjacent;
        var length = connected.length;
        if (length === 0) {//the vertex is isolated
            return false;
        }
        for (var i = 0; i < length; i++) {
            if (walk(connected[i])) {//try each adjacent vertex
                path.push(vertex);
                return true;
            }
        }
    }
 
    function printPath(){
    var footprint = '';
    var length = path.length;
    for (var i = length - 1; i > -1; i--) {
        footprint += path[i].id;
        footprint += i === 0 ? '' : ' > ';
    }
    print(footprint);
}

    if (walk(entry)) {
        printPath();
    }
    else {
        print('出不去！');
    }
}我们可以试验一下这段代码走迷宫的能力。

[javascript]
function testMaze(){ 
    var g=Graph(); 
    g.addIds([1, 2, 3, 4, 5, 6]); 
    g.connect(1, 2); 
    g.connect(1, 3); 
    g.connect(1, 4); 
    g.connect(2, 3); 
    g.connect(3, 5); //你可以画出这个图  
    walkOut(g.vertices[1], g.vertices[5]);//1 > 2 > 3 > 5  
    walkOut(g.vertices[1], g.vertices[6]);//出不去！  
    walkOut(g.vertices[2], g.vertices[5]);//2 > 1 > 3 > 5  
} 

function testMaze(){
 var g=Graph();
 g.addIds([1, 2, 3, 4, 5, 6]);
 g.connect(1, 2);
 g.connect(1, 3);
 g.connect(1, 4);
 g.connect(2, 3);
 g.connect(3, 5); //你可以画出这个图
 walkOut(g.vertices[1], g.vertices[5]);//1 > 2 > 3 > 5
 walkOut(g.vertices[1], g.vertices[6]);//出不去！
 walkOut(g.vertices[2], g.vertices[5]);//2 > 1 > 3 > 5
}在现实生活中，我们当然也可以用这种笨办法走出任何一个可能走出的迷宫，只要你用笔和便签纸在每一个岔路口记下你选择的路线。