递归

本文主要是介绍递归，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

递归能够解决的问题：

1）数学问题：8皇后，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题

2）算法也会用到：快排，归并排序，二分查找，分治算法

3）将用栈解决的问题换成递归比较简洁

递归需要遵守的规则：

　　1）执行一个方法，就创建一个新的受保护的独立空间（栈空间）

　　2）方法的局部变量是独立的，不会相互影响，比如n变量

　　3）如果方法中使用的是引用类型变量（比如数组），就会共享该引用类型的数据

　　4）递归必须向退出递归的条件逼近，否则就是无限递归，

　　5）当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，

同时当方法执行完毕或者返回时，该方法也就执行完毕

　　迷宫问题：

  1 public class MiGong {
  2     public static void main(String[] args) {
  3         //先创建一个二维数组，模拟迷宫
  4         //地图
  5 
  6         int[][] map = new int[8][7];
  7         //使用1 表示墙
  8         //上下全部置为1
  9         for (int i = 0; i < 7; i++) {
 10             map[0][i]=1;
 11             map[7][i]=1;
 12         }
 13         for (int i = 0;i<8; i++){
 14             map[i][0] =1 ;
 15             map[i][6] =1;
 16         }
 17         //设置挡板，1表示
 18         map[3][1] = 1;
 19         map[3][2] = 1;
 20         //map[1][2] = 1;
 21         //map[2][2] = 1;
 22 
 23 
 24         //输出地图
 25         System.out.println("地图的情况");
 26         for (int i = 0; i < 8 ; i++) {
 27             for (int j = 0; j < 7; j++) {
 28                 System.out.print(map[i][j]+" ");
 29             }
 30             System.out.println();
 31         }
 32         //使用递归给小球找路
 33         setWay2(map,1,1);
 34         //输出新的地图，小球走过，并标识过的递归
 35         System.out.println("小球走过，并标识过的地图");
 36         for (int i = 0; i < 8 ; i++) {
 37             for (int j = 0; j < 7; j++) {
 38                 System.out.print(map[i][j]+" ");
 39             }
 40             System.out.println();
 41         }
 42 
 43     }
 44     //
 45 
 46     //使用递归回溯来给小球找路
 47     //说明：
 48     //1.map 表示地图
 49     //2.i,j 表示从地图的哪个位置开始出发（1,1）
 50     //3. 如果小球能到map[6][5]位置，则说明通路找到
 51     //4.约定：当map[i][j]为0时表示该点没有走过，当为1表示墙，为2表示通路可以走，为3表示该位置已经走过，但是走不通
 52     //5.走迷宫时需要确定一个策略，先 下-右-上-左，如果该点走不通再回溯
 53     /**
 54      *
 55      *
 56      * @param map
 57      * @param i 从哪个位置开始找
 58      * @param j
 59      * @return  如果找到通路，就返回true，否则返回false
 60      */
 61     public static boolean setWay(int[][] map, int i,int j){
 62         int index =0;
 63         if (map[6][5] == 2){ //通路已找到
 64             return true;
 65         }else{
 66             if (map[i][j] == 0){//如果当前这个点还没走过
 67                 //按照策略
 68                 map[i][j] =2 ;//假定该点可以走通
 69 
 70                 if (setWay(map,i+1,j)){//向下走
 71                     return true;
 72                 }else if (setWay(map,i,j+1)){//向右走
 73                     return true;
 74                 }else if(setWay(map,i-1,j)){//向上走
 75                     return true;
 76                 }else if (setWay(map,i,j-1)){//向左走
 77                     return true;
 78                 }else {
 79                     //说明该点走不通
 80                     map[i][j]=3;
 81                     return false;
 82                 }
 83             }else { //如果map[i][j] != 0,可能是1,2,3
 84                 return false;
 85 
 86             }
 87         }
 88     }
 89 
 90 
 91     //修改找路策略，上右下左
 92     public static boolean setWay2(int[][] map, int i,int j){
 93         if (map[6][5] == 2){ //通路已找到
 94             return true;
 95         }else{
 96             if (map[i][j] == 0){//如果当前这个点还没走过
 97                 //按照策略
 98                 map[i][j] =2 ;//假定该点可以走通
 99                 if (setWay2(map,i-1,j)){//向下走
100                     return true;
101                 }else if (setWay2(map,i,j+1)){//向右走
102                     return true;
103                 }else if(setWay2(map,i+1,j)){//向上走
104                     return true;
105                 }else if (setWay2(map,i,j-1)){//向左走
106                     return true;
107                 }else {
108                     //说明该点走不通
109                     map[i][j]=3;
110                     return false;
111                 }
112             }else { //如果map[i][j] != 0,可能是1,2,3
113                 return false;
114 
115             }
116         }
117     }
118 
119 }

八皇后：

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

这篇关于递归的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！