1、源码

  1. package com.study.recursion;
  3. public class MiGong {
  5.     public static void main(String[] args) {
  7.         //创建一个二维数组模拟迷宫
  8.         int[][] map = new int[8][7];
  9.         // 1 表示墙
  10.         //将第一行和第八行全部置为1
  11.         for (int i = 0; i < 7; i++) {
  12.             map[0][i] = 1;
  13.             map[7][i] = 1;
  14.         }
  15.         //将第一列和第七列全部置为1
  16.         for (int i = 0; i < 8; i++) {
  17.             map[i][0] = 1;
  18.             map[i][6] = 1;
  19.         }
  20.         //将第四行第二列和第四行第三列置为1;
  21.         map[3][1] = 1;
  22.         map[3][2] = 1;
  23.         //遍历数组
  24.         System.out.println("迷宫为：");
  25.         for (int i = 0; i < 8; i++) {
  26.             for (int j = 0; j < 7; j++) {
  27.                 System.out.print("\t"+map[i][j]);
  28.             }
  29.             System.out.println();
  30.         }
  31.         setWay(map,1,1);
  32.         System.out.println("小球走出后的迷宫：");
  33.         for (int i = 0; i < 8; i++) {
  34.             for (int j = 0; j < 7; j++) {
  35.                 System.out.print("\t"+map[i][j]);
  36.             }
  37.             System.out.println();
  38.         }
  40.     }
  42.     /**
  43.      * 使用递归回溯来给小球找路
  44.      * 说明：
  45.      * 1.map表示地图
  46.      * 2.i,j表示从地图哪个位置出发（1，1）
  47.      * 3.如果小球能到map[6][5],说明小球找到通路
  48.      * 4.约定：当map[i][j] 为0表示该点没有走过，为1表示墙，为2表示通路可以走，为3表示该点已经走过，但是不通
  49.      * 5.在走迷宫时需要制定一个策略（方法）：下->右->上->左，如果该点走不通，在回溯
  50.      * @param map 表示地图
  51.      * @param i 从哪个位置开始走
  52.      * @param j
  53.      * @return 如果是通路，返回true，否则返回false；
  54.      */
  55.     public static boolean setWay(int[][] map,int i,int j){
  57.         if (map[6][5] == 2){//通路已经找到
  58.             return true;
  59.         }else {
  60.             if (map[i][j]==0){//表示该点没有走过
  61.                 map[i][j] = 2;
  62.                 if (setWay(map, i+1, j)){//向下走
  63.                     return true;
  64.                 }else if(setWay(map, i, j+1)){//向右走
  65.                     return true;
  66.                 }else if(setWay(map, i-1, j)){//向上走
  67.                     return true;
  68.                 }else if(setWay(map, i, j-1)){//向左走
  69.                     return true;
  70.                 }else {
  71.                     map[i][j] = 3;
  72.                     return false;
  73.                 }
  74.             }else {//如果map[i][j]!=0,可能是1,2,3
  75.                 return false;
  76.             }
  77.         }
  79.     }
  81. }

2、运行结果

图片.png

3、总结

递归需要遵守的重要规则

  1. 执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
  2. 方法的局部变量是独立的，不会相互影响, 比如n变量
  3. 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
  4. 递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了:)
  5. 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。