More examples of recursion in JavaScript

More examples

The second recursive example is to find the greatest common divisor of two natural numbers (have you ever gone back to your nostalgic middle school days). The program below uses the classic euclidean division method.

[javascript]
//greatest common divisor
//Assume a and b are both positive integers
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
//Assumption a and b are both positive integers
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);
}
In addition to the above conditions or solutions that can be converted into mathematical recursive definition calculations, the recursive method is also applicable to the data involved Structures are problems defined in a recursive form, such as linked lists, graphs, trees, etc.

Now let’s look at a maze example. The maze can be abstracted into a mathematical diagram. Each fork in the road is a point, and the roads in between are edges. Two special points are defined as entrance and exit respectively.

The following are points and graphs defined in Javascript. Each point contains an id as a number and label, and adjacent points are saved in an array. The graph has a method for adding points, a more convenient method of directly adding point IDs, and a method for adding edges.

[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 }
vertices[vertex.id]=vertex;
}
//create vertices from ids and add them to the graph
function addIds(ids){
var id;
for (var i=0; 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 ){
                                                                                    who’ who’ who’ who’ who’ who’s’ who’s’,         v1.adjacent.push(v2); 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    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   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
}在现实生活中，我们当然也可以用这种笨办法走出任何一个可能走出的迷宫，只要你用笔和便签纸在每一个岔路口记下你选择的路线。