1、递归概念

自己调用自己每次调用传入的变量都不同

2、递归怎么调用的

 

 

 3、递归应该遵守的规则

执行一个方法时，就创建一个新的受保护的独立空间（栈空间）方法的局部变量是独立的，不会相互影响，比如n变量递归必须有退出的条件，否则就是无限递归，报stackOverFloweError（栈溢出错误）当一个万法执行完毕，或者遇到returm，就会返回，守谁调用，就将结果返回给谁如果万法中使用的是引用类型变量（比如数组），就会共享该引用类型的数据

4、迷宫问题解决

　　

 

 　

　先用二维数组模拟出表格，给部分表格赋值1来说明是墙壁（红色部分）

　

public static void main(String[] args) { int[][] map=new int[10][10]; //设置墙体 for (int i=0;i<10;i++){ map[0][i]=1; map[i][0]=1; map[i][9]=1; map[9][i]=1; } //设置障碍 map[3][1]=1; map[3][2]=1; //map[1][2]=1; //map[2][2]=1; //打印表格 for (int i=0;i<10;i++){ for (int j=0;j<10;j++){ System.out.print(map[i][j]+" "); } System.out.println(); } //进行寻路 setWay(map,1,1); //打印表格 System.out.println("寻路完成"); for (int i=0;i<10;i++){ for (int j=0;j<10;j++){ System.out.print(map[i][j]+" "); } System.out.println(); } }

 

设置寻路的方法，按照设置的策略（如下右上左）来逐个进行递归，如果能走通，这条路线标识为2，走不通（无法到达指定终点）递归进行回溯，将走过的路置为3

判断这条路是否可行： 1是墙，2是走过的路，3是走不通的路

//设置策略方法（下右上左） public static boolean setWay(int[][] map,int i,int j){ //map表示数组地图，i，j表示坐标 if (map[8][8]==2){//开始前判断该节点是否找到 return true; }else{ if (map[i][j]==0){ map[i][j]=2; //走过的地方都先置为2，回溯后置为3 if (setWay(map,i+1,j)){ //下 return true; }else if (setWay(map,i,j+1)){ //右 return true; }else if (setWay(map,i-1,j)){ //上 return true; }else if (setWay(map,i,j-1)){ //左 return true; }else{ map[i][j]=3; //查找失败时，这个路线回溯并设置为3 return false; } }else{ return false; } }

运行结果是：

 

 

 注意：选择的策略不同，迷宫的查找路径就不同　

 

如何获取最短路径？

可以统计不同的策略生成的路线，通过获取策略的路径长度来比较出最短路径的策略

如上面这种策略，统计路径长度

//统计路长 int count=0;//长度 for (int i=0;i<10;i++){ for (int j=0;j<10;j++){ if (map[i][j]==2){ //当路径标识为2时为可用 count+=1; } } } System.out.println("路径长"+count);

 

　　　　

　　　　

转载于:https://www.cnblogs.com/han200113/p/11581386.html

相关资源：三维迷宫，支持替身通过一定交互手段在迷宫中漫游