Java递归应用

小鱼儿 2021-11-09 07:28 304阅读 0赞

## 一、概念 ##

简单的说： **递归就是方法自己调用自己**

**　递归有助于解决复杂的问题**，可以让代码变得简洁

## 二、能解决什么样的问题 ##

![1007094-20190802201754300-1074948892.png][]

## 三、递归需要遵守的重要规则 ##

![1007094-20190802201935033-1432691369.png][]

## 四、迷宫问题 ##

![1007094-20190802202116507-324525072.png][]

**　说明：**

1）小球得到的路径，和程序员设置的查找策略有关，即：上 -> 下 -> 左 -> 右

2)  在得到小球路径时，可以先使用（上下左右），在改为（上右下左），看路径是否有变化

3）测试回溯现象

4）最短路径求法？

**　代码：　**

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

## 五、八皇后问题（回溯算法） ##

##  　**　1、概述** ##

[八皇后][Link 1]问题，是一个古老而著名的问题，是[回溯算法][Link 2]的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即**任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法**。 [高斯][Link 3]认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用**图论的方法解出92**种结果。计算机发明后，有多种计算机语言可以解决此问题。

![1007094-20190802202908349-2082184430.png][]

## 　　2、思路分析　![1007094-20190802202940184-674257724.png][] ##

## 　　3、说明 ##

理论上应该创建一个二维数组来表示棋盘，但实际可以通过算法，用一个一位数组即可解决问题

**arr\[8\] = \{0, 4, 7,5,2,6,1,3\}，对应的下标表示第几行，即第几个皇后，arr\[i\] = val, val 表示第i+1个皇后，放在i+1行的第val+1列**

## 　　4、代码 ##

1 public class Queen8 {
     2     //定义一个max表示共有多少个皇后8
     3     final static int max = 8;
     4     //定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
     5     static int[] arr = new int[max];
     6     //记录不冲突的次数
     7      static int count;
     8     //总判断次数
     9     static int sumCount;
    10 
    11     public static void main(String[] args) {
    12         check(0);
    13         System.out.printf("共有%d种走法，一共判断%d次\n",count,sumCount);
    14     }
    15 
    16     //编写一个方法，放置第n个皇后
    17     //特别注意： check 是 每一次递归时，进入到check中都有  for(int i = 0; i < max; i++)，因此会有回溯
    18     public static void check(int n) {
    19         //n = 8 , 其实8个皇后就既然放好
    20         if (n == max) {
    21             print();
    22             return;
    23         }
    24         //依次放入皇后，并判断是否冲突
    25         for (int i = 0; i < max; i++) {
    26             //先把当前这个皇后 n , 放到该行的第1列
    27             arr[n]=i;
    28             //判断当放置第n个皇后到i列时，是否冲突
    29             if(judge(n)){ // 不冲突
    30                 //接着放n+1个皇后,即开始递归
    31                 check(n+1);
    32             }
    33             //如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行得 后移的一个位置
    34         }
    35 
    36     }
    37 
    38     //查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
    39     public static boolean judge(int n) {
    40         sumCount++;
    41         // 说明
    42         //1. array[i] == array[n]  表示判断 第n个皇后是否和前面的n-1个皇后在同一列
    43         //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
    44         // n = 1  放置第 2列 1 n = 1 array[1] = 1
    45         // Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
    46         //3. 判断是否在同一行, 没有必要，n 每次都在递增
    47         for (int i = 0; i <n ; i++) {
    48             if(arr[i]==arr[n]||Math.abs(arr[n]-arr[i])==Math.abs(n-i)){
    49                 return false;
    50             }
    51         }
    52         return true;
    53     }
    54 
    55     //写一个方法，可以将皇后摆放的位置输出
    56     public static void print() {
    57         count++;
    58         for (int i = 0; i < arr.length; i++) {
    59             System.out.print(arr[i]+"\t");
    60         }
    61         System.out.println();
    62     }
    63 }

[1007094-20190802201754300-1074948892.png]: /images/20211109/47a80f59db244a40875b2102f27c0771.png
[1007094-20190802201935033-1432691369.png]: /images/20211109/0ccbeacfa40d4f4ea36306fe88a61081.png
[1007094-20190802202116507-324525072.png]: /images/20211109/251abd309ebb4dceaf32bef2c05e6a44.png
[Link 1]: https://baike.baidu.com/item/%E5%85%AB%E7%9A%87%E5%90%8E
[Link 2]: https://baike.baidu.com/item/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95/9258495
[Link 3]: https://baike.baidu.com/item/%E9%AB%98%E6%96%AF/24098
[1007094-20190802202908349-2082184430.png]: /images/20211109/4f4f1dfba02549f2966e65a2b3fe4a38.png
[1007094-20190802202940184-674257724.png]: /images/20211109/95a20e017f964ef1bdf86607fe5a9929.png