脚本宝典收集整理的这篇文章主要介绍了javascript代码实例教程-JavaScript的递归之更多例子，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。小宝典致力于为广大程序猿（媛）提供高品质的代码服务，请大家多多光顾小站，小宝典在此谢过。
更多例子
第二个递归的例子是求两个自然数的最大公约数（有没有回到令人怀念的中学时代）。下面的程序用的是经典的辗转相除法。
[javascript]
//greatest common pisor
//假定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 pisor
//假定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);
}
除了上面这些条件或者解法可以转化为数学的递归定义的计算，递归方法还适用于其所涉及的数据结构即是以递归形式定义的问题，比如链表、图、树等等。
现在我们来看一个迷宫的例子。迷宫可以抽象成一副数学上的图，每个岔路口是一个点，其间的路是边。两个特殊的点，分别被定义成入口和出口。
下面是用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
}在现实生活中，我们当然也可以用这种笨办法走出任何一个可能走出的迷宫，只要你用笔和便签纸在每一个岔路口记下你选择的路线。
觉得可用，就经常来吧！ 脚本宝典 欢迎评论哦！ js脚本，巧夺天工，精雕玉琢。小宝典献丑了！
以上是脚本宝典为你收集整理的javascript代码实例教程-JavaScript的递归之更多例子全部内容，希望文章能够帮你解决javascript代码实例教程-JavaScript的递归之更多例子所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。