递归的概念以及迷宫问题

1、概念

递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。并且递归用到了虚拟机栈

2、能解决的问题

数学问题

• 八皇后问题
  
• 汉诺塔
  
• 求阶乘
  
• 迷宫问题
  
• 球和篮子
  

各种排序算法
3、规则

• 方法的变量是独立的，不会相互影响的
  
• 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据
  
• 递归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError
  
• 当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或
  者返回时，该方法也就执行完毕
  

4、迷宫问题

思路

• 用一个二维矩阵代表地图
  
  
  
  • 1代表边界
    
  • 0代表未做过该地点
    
  • 2代表走过且能走得通
    
  • 3代表走过但走不通
    
  
  
• 设置起点和终点以及每个地点的行走策略
  
  
  
  • 行走策略指在该点所走的方向的顺序，如 下->右->上->左（调用寻找路径的方法，使用递归）
    
  
  
• 每次行走时假设该点能够走通，然后按照策略去判断，如果所有策略判断后都走不通，则该点走不通
  

图解
初始地图，假设圆点为终点

 
 如以下->右->上->左的策略，路线如下

 
 代码

1. public class MiGong {
2.     //用0表示没有走过的路,用1表示墙
3.     public static void main(String[] args) {
4.         int[][] map = new int[8][7];//创建地图
5.         
6.         //设置地图的墙体,用1来表示
7.         for (int i = 0; i < 7; i++){
8.             map[0][i] = 1;
9.             map[7][i] = 1;
10.         }
11.         for (int i = 0; i < 8; i++){
12.             map[i][0] = 1;
13.             map[i][6] = 1;
14.         }
15.         map[3][1] = 1;
16.         map[3][2] = 1;
18.         System.out.println("迷宫地图:");
19.         for (int i = 0; i < map.length; i++){
20.             for (int j = 0; j < map[0].length; j++){
21.                 System.out.print(map[i][j]+" ");
22.             }
23.             System.out.println();
24.         }
26.         setWay(map,1,1);
27.         System.out.println("启动走迷宫后:");
28.         for (int i = 0; i < map.length; i++){
29.             for (int j = 0; j < map[0].length; j++){
30.                 System.out.print(map[i][j]+" ");
31.             }
32.             System.out.println();
33.         }
34.     }
36.     /**
37.      * 用2表示走过的路,用3表示走过且不能继续走下去的路
38.      * @param map 表示地图
39.      * @param i   表示第i行开始找
40.      * @param j   表示第j列开始找
41.      * @return    返回true的时候表示可以走,返回false的时候表示不能走
42.      */
43.     public static boolean setWay(int[][] map, int i, int j){
44.         if (map[6][5] == 2){//设map[6][5]这个位置是迷宫终点,当终点为2的时候表示迷宫走通了
45.             return true;
46.         }else {
47.             if (map[i][j] == 0){
48.                 map[i][j] = 2;
49.                 //制定策略:下->右->上->左
50.                 if (setWay(map,i+1,j)){
51.                     return true;
52.                 }else if (setWay(map,i,j+1)){
53.                     return true;
54.                 }else if (setWay(map,i-1,j)){
55.                     return true;
56.                 }else if (setWay(map,i,j-1)){
57.                     return true;
58.                 }else {
59.                     map[i][j] = 3;
60.                     return false;
61.                 }
62.             }else {//非0的情况可能是1、2、3,直接false
63.                 return false;
64.             }
65.         }
66.     }
67. }

复制代码

　　结果：

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！