提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
目录
前言
一、递归是什么
二、迷宫的实现
三、对递归在此案例中使用的理解
四、不同找路策略对最终迷宫盘面的影响
总结
前言
迷宫找路问题是经典的递归的应用。本迷宫找路策略为在网上学习，编程小白在此分享自己的学习感悟和对编程知识点的理解。
一、递归是什么
我目前对递归的理解是：通过自己调用自己的方式，在jvm内存里不断开辟新的独立栈。通过传入变化的参数 不断逼近不会再调用自己的条件，停止递进的深入。将最顶层栈的方法调用结果逐层返回给调用者，实现结果的回归。
二、迷宫的实现
这里采用最简单的实现方式，即用二维数组来表示迷宫的盘面。0为道路，1为障碍物。
设置一个8*8的迷宫盘面，将迷宫的四边置1，代码如下：
int[][] map = new int[8][8]; //创建一个8*8的迷宫盘面
for(int i = 0;i < 8;i++){ //将四边的格子置1
map[0][i] = 1;
map[7][i] = 1;
map[i][0] = 1;
map[i][7] = 1;
}设置迷宫中的墙，代码如下：
map[3][1] = 1;
map[3][2] = 1;
map[2][2] = 1;
//map[1][2] = 1;
map[2][4] = 1;
map[2][5] = 1;
map[3][4] = 1;
map[3][5] = 1;
map[5][2] = 1;
map[5][3] = 1;
map[5][4] = 1;
map[5][5] = 1;
map[5][6] = 1;设置好的迷宫初始盘面如下：
迷宫的起点和终点为左上角和右下角，即数组元素map[1][1]和map[6][6]。
接下来就是使用递归，找到从起点到终点的路径。
规定：将可达的道路设置为2，不可达的道路设置为3，代码如下：
public boolean findWay(int[][] map,int i,int j){ //找路方法 if(map[6][6] == 2){ return true; //终点可走表示以找到通路 }else{ if(map[i][j] == 0){ //找路策略 map[i][j] = 2; if(findWay(map,i+1,j)){//先下 return true; }else if(findWay(map,i,j-1)){//左 return true; }else if(findWay(map,i-1,j)){//上 return true; }else if(findWay(map,i,j+1)){//右 return true; }else{ map[i][j] = 3; //是死路 return false; } }else{ //非0表示不可走 return false; } } }
基本思路为：
1.将当前迷宫map和当前所在位置(i , j)传入找路方法当中
2.终点map[6][6]以置为2，返回true 表示找到通向迷宫出口路径
3.走到为0的位置，首先将此位置置为2，再使用递归的思想，调用自己，通过改变将要走的位置实现方法的递进
4.如果当前位置的上下左右都走不通，则将此位置置为3，表示不可达
迷宫找路演示结果如下：
完整代码如下：
/*
走迷宫问题：
1.用二维数组来作为迷宫盘面
2.0为道路，1为障碍物
3.写一个找路方法，找到能从起点抵达终点的路径
*/
public class MiGong{
public static void main(String[] args){
int[][] map = new int[8][8]; //创建一个8*8的迷宫盘面
for(int i = 0;i < 8;i++){ //将四边的格子置1
map[0][i] = 1;
map[7][i] = 1;
map[i][0] = 1;
map[i][7] = 1;
}
map[3][1] = 1;
map[3][2] = 1;
map[2][2] = 1;
//map[1][2] = 1;
map[2][4] = 1;
map[2][5] = 1;
map[3][4] = 1;
map[3][5] = 1;
map[5][2] = 1;
map[5][3] = 1;
map[5][4] = 1;
map[5][5] = 1;
map[5][6] = 1;
System.out.println("迷宫的初始盘面为");
for(int i = 0;i < map.length;i++){
for(int j = 0;j < map[i].length;j++){
System.out.print(map[i][j] + " ");
}
System.out.println();
}
To t = new To();
boolean isTo = t.findWay(map,1,1);
if(isTo){
System.out.println("找到通路! \n出迷宫路线如下：");
for(int i = 0;i < map.length;i++){
for(int j = 0;j < map[i].length;j++){
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}else{
System.out.println("未找到通路!");
}
}
}
class To{
// 规定：2 为可走；3 为不可达
public boolean findWay(int[][] map,int i,int j){ //找路方法
if(map[6][6] == 2){
return true; //终点可走表示以找到通路
}else{
if(map[i][j] == 0){ //找路策略
map[i][j] = 2;
if(findWay(map,i+1,j)){//先下
return true;
}else if(findWay(map,i,j-1)){//左
return true;
}else if(findWay(map,i-1,j)){//上
return true;
}else if(findWay(map,i,j+1)){//右
return true;
}else{
map[i][j] = 3; //是死路
return false;
}
}else{ //非0表示不可走
return false;
}
}
}
}三、对递归在此案例中使用的理解
递归在此案例中的使用可以理解为，在不知道终点可不可达的情况下，按找路策略对所有可能通向终点的道路的试探，直到找到可以将终点置为2的路径
每一次递归的调用都是 在当前位置下对所有可走道路的试探。一次次的往后走去，直到发现上下左右都不可走时即将当前位置置为3，并将false逐层返回到最近一个还有可走方向选择的位置，继续向还为0的可走道路探寻
四、不同找路策略对最终迷宫盘面的影响
前面所演示的 以下、左、上、右为顺序的找路策略所找到的路径是这样的：
而如果换成下、右、上、左的策略，结果将会变成这样：
可见原本不是通向终点的右边一条路的位置都被置为了3，即在下的优先级高于左和右为前提时，右的优先级高于左，让处于map[4][3]位置时 优先选择了向右走，最终发现这条路到map[1][4]位置时以无路可走，所以回溯到map[4][3]位置选择剩下的左方向 抵达终点。
如果将起点周围都设置成障碍物，没有一条路可以抵达终点，那么将显示：
总结
本案例中体现了递归的递进和回溯，使用递归探寻可能通向终点的道路，如果所找道路为死路将回溯到最近一个还有未试探路的位置继续探寻。
可见递归适用于不断变化的参数所产生出的新的条件供递归的调用者判断，最终递归方法产生出的结果逐层返回给调用者使用以产生新的结果，最终返回给main方法里的递归方法调用者的场景。
这些就是我这个编程小白目前对递归的浅显认知。
更多推荐
Java代码实现迷宫找路
发布评论