1. 应用实例

  • 迷宫问题（回溯与递归）

    2. 概念

  • 可以理解为：

    • 递归就是方法自己调用自己，每次调用时传入不同的变量。递归有助于编程者解决复杂的问题，同时可以让代码更加简洁。

      3. 递归调用机制

  • 实际案例说明

  • 打印问题

    1.   public static void main(String[] args) {
    2.       print(10);
    3.       System.out.println("===");
    4.       print(13);
    5.   }
    7.   public static void print(int n){
    8.       if (n>10){
    9.           print(n-1);
    10.       }
    11.       System.out.println("n = " + n);
    12.   }
    • 每个方法调用时，会开辟一个独立的栈空间
    • 在调用print(13)时，发生了递归；
    • 此时满足条件进入到if里面，调用print(12)，这样就又开辟了一个空间去处理print(12)
    • print(12)又会进入if，进入print(11)
    • …
    • 直到最后print(10)，无法满足if条件，直接进行打印，该print(10)结束，
    • 此时表示print(11)中的if代码块处理完成了，这样print(11)也进行打印n
    • …
    • 直到最后print(13)中的if块直接完成，然后完成打印n，这样print(13)的调用就结束了
    • 此过程中，调用一次print(13)，却发生了4次print方法的调用，这里就形成了递归

  • 阶乘问题

    • 给定一个数，求其阶乘，那么设置一个方法res，当n>1时，return n*res(n-1)即可

      class FactorialUrl{
public int factorial(int n) throws Exception {
   if (n<0){
       throw new Exception("请输入一个大于等于0的整数");
   }else if (n==0||n==1){
       return 1;
   }else {
       return n*factorial(n-1);
   }
}
}

    • 同理这里的return n*factorial(n-1);也用到了递归

      4. 递归能解决的问题

  • 各种数学问题：包括，八皇后，汉诺塔，阶乘，迷宫，球和篮子…

  • 各种算法也利用递归：包括，快速排序，归并排序，二分查找，分支算法…

    5. 递归需要遵守的规则

  • 执行一个方法，会开辟一个新的独立的栈空间（保证每一次递归方法处理完全独立）。

  • 方法的局部变量相互独立，不受影响。
  • 如果方法中使用的是引用类型，就会共享该引用类型的数据。
  • 递归必须向退出递归的方向逼近，否则无限递归，该处理就无意义，并且会出现StackOverFlowError（栈溢出错误）。

  • 当一个方法执行完毕，或者遇到return，就会返回，返回给调用者；调用者处理完成会交给更下一层调用者，直到最后最底层调用者处理完成，表示递归结束。

    6. 迷宫问题

    6.1 解决思路：

  • 使用递归和回溯，这里设置0为未走过的路，1为墙，2为走得通的位置并且能到达终点，3为该点能走但是无法到达终点的位置。

  • 递归：

    • 结束的标志为当所设置的终点标记为2时，表示走通，直接返回true，否则就继续探索
    • 如果碰到的该点是1或者3那么直接返回false，因为该路无法走通
    • 如果是0，表示未探索过，那么设置该点为2，进行继续探索，如果所有方向探索都没有结果，那么设置该位置为3，并返回false

  • 回溯：

    • 这里返回false；就是一个回溯，回溯到上一个调用者，然后该调用者开始进行其他策略的探索，直到探索失败，或者成功后返回给它的上一个调用者。

      6.2 实现

      /**
*  "0" 表示未走过
*  "1" 表示墙
*  "2" 表示走得通
*  "3" 表示当前位置能过去,但是走不到最终点
*/
public class MiGong {
public int[][] map;
// 初始化地图,但是这里没有处理迷宫的墙, 需要调用者自己添加
public MiGong(int row,int col){
   map = new int[row][col];
   for (int i=0;i<map.length;i++){
       map[i][0] = 1;
       map[i][map.length-1] = 1;
   }
   for (int i=0;i<map[0].length;i++){
       map[0][i] = 1;
       map[map[0].length-1][i] = 1;
   }
}

/**
*  策略: 右->下->上->左
*/
public boolean setWay(int[][] map,int i,int j){
   // 设置为7*7的迷宫, 终点为map[5][5];
   // 这里默认设置终点为map[map.length-2][map[0].length-2]
   if(map[map.length-2][map[0].length-2] == 2){
       return true;
   }else {
       if (map[i][j] == 1 || map[i][j]==3){
           return false;
       }
       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;
       }
   }
}

// 显示迷宫
public void show(){
   for (int i=0;i<map.length;i++){
       for (int j=0;j<map[0].length;j++){
           System.out.printf("%d\t",map[i][j]);
       }
       System.out.println();
   }
}
}

  • 这里行走的策略决定最终得到的路径。

7. 八皇后问题

  • 一个8*8的棋盘，放置8个棋子，要求每个棋子不能在同一行，同一列以及斜对角线上。

    7.1 解决思路

  • 当选择一个点后，需要判断该点是否能放置（根据八皇后规则进行判断），如果可以那么继续以该点进行探索（递归），从每一行的0位置开始放置，找到一个能够放置的位置，直到8个位置放置完毕。

  • 判断位置是否可放的策略：每一次探索会先将该位置列坐标放到数组中，然后会去判断，第n行与前面几行的所有列坐标是否相同，如果相同表示在同一列，不满足条件；如果列坐标之差的绝对值等于行坐标之差的绝对值，那么也不满足条件，进行返回false。

  • 递归：

    • 结束条件： 当结果数组放满，或者当探索的行数到达8（也就是第9行）那么停止。

  • 这里之所以能够将所有结果都进行输出，是因为放置每个棋子都是从0到7for循环探索，不管成功与否，每个位置都要探索；探索成功，输出结果，进行return；结束探索；如果探索不成功，那么返回上一层调用者，上一层调用者进行下一次循环，找到另一个位置继续探索。

    7.2 实现

    ```java public class Queue8 {

    int[] res = new int[8];

    public void check(int n){

      if (n==8){
      System.out.println(Arrays.toString(res));
      return;
  }
  for (int i=0;i<8;i++){
      res[n] = i;
      if (adjust(n)) check(n+1);
  }

    }

    public boolean adjust(int n){

      for (int i=0;i<n;i++){
      if (res[i] == res[n] || Math.abs(n-i) == Math.abs(res[n]-res[i])) return false;
  }
  return true;

    } }

```