递归的概念以及迷宫问题
1、概念
递归就是方法自己调用自己 ,每次调用时 传入不同的变量 .递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。并且递归用到了 虚拟机栈
2、能解决的问题
数学问题
- 八皇后问题
- 汉诺塔
- 求阶乘
- 迷宫问题
- 球和篮子
各种排序算法
3、规则
-
方法的变量是独立的，不会相互影响的
-
如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据
-
递归 必须向退出递归的条件逼近 ，否则就是无限递归，出现 StackOverflowError
-
当一个方法执行完毕，或者遇到 return，就会返回， 遵守谁调用，就将结果返回给谁 ，同时当方法执行完毕或
者返回时，该方法也就执行完毕
4、迷宫问题
思路
- 用一个二维矩阵代表地图
- 1代表边界
- 0代表未做过该地点
- 2代表走过且能走得通
- 3代表走过但走不通
- 设置起点和终点以及每个地点的 行走策略
- 行走策略指 在该点所走的方向的顺序 ，如 下->右->上->左（调用寻找路径的方法，使用递归）
- 每次行走时假设该点能够走通，然后按照策略去判断，如果所有策略判断后都走不通，则 该点走不通
图解
初始地图，假设圆点为终点
如以下->右->上->左的策略，路线如下
代码
public class MiGong {
//用0表示没有走过的路,用1表示墙
public static void main(String[] args) {
int[][] map = new int[8][7];//创建地图
//设置地图的墙体,用1来表示
for (int i = 0; i < 7; i++){
map[0][i] = 1;
map[7][i] = 1;
}
for (int i = 0; i < 8; i++){
map[i][0] = 1;
map[i][6] = 1;
}
map[3][1] = 1;
map[3][2] = 1;
System.out.println("迷宫地图:");
for (int i = 0; i < map.length; i++){
for (int j = 0; j < map[0].length; j++){
System.out.print(map[i][j]+" ");
}
System.out.println();
}
setWay(map,1,1);
System.out.println("启动走迷宫后:");
for (int i = 0; i < map.length; i++){
for (int j = 0; j < map[0].length; j++){
System.out.print(map[i][j]+" ");
}
System.out.println();
}
}
/**
* 用2表示走过的路,用3表示走过且不能继续走下去的路
* @param map 表示地图
* @param i 表示第i行开始找
* @param j 表示第j列开始找
* @return 返回true的时候表示可以走,返回false的时候表示不能走
*/
public static boolean setWay(int[][] map, int i, int j){
if (map[6][5] == 2){//设map[6][5]这个位置是迷宫终点,当终点为2的时候表示迷宫走通了
return true;
}else {
if (map[i][j] == 0){
map[i][j] = 2;
//制定策略:下->右->上->左
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;
return false;
}
}else {//非0的情况可能是1、2、3,直接false
return false;
}
}
}
}
结果：
