君臣一梦,今古空名。但远山长,云山乱,晓山青。
——苏轼《行香子》
递归
递归:指在当前方法内调用自己的这种现象,每次调用时传入不同的变量。
1. 计算 1+2+3+….+n的和
1 2 3 4 5 6 7 8 9 10 11 12 13
| @Test public void test2() { int n = 100; int sum = sum( n ); System.out.println( "sum = " + sum ); }
public int sum(int n) { if (n == 1) { return 1; } return sum( n - 1 ) + n; }
|
2. 递归阶乘
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| @Test public void test3() { int n = 10; int value = getValue( n ); System.out.println( "value = " + value ); } private int getValue(int n) { if (n == 1) { return 1; } return getValue( n - 1 ) * n; }
|
3. 斐波那契数列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
|
@Test public void test4() { int n = 10; int sum = getRabbit( n ); System.out.println( "sum = " + sum ); } private int getRabbit(int n) { if (n == 1 || n == 2) { return 1; } return getRabbit( n - 1 ) + getRabbit( n - 2 ); }
|
4. 爬山问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
@Test public void test5() { int num = 40; int value = getTimes( num ); System.out.println( "value = " + value ); }
private int getTimes(int num) { if (num == 1) return 1; if (num == 2) return 2; if (num == 3) return 4; return getTimes( num - 1 ) + getTimes( num - 2 ) + getTimes( num - 3 ); } }
|
5. 打印多级目录
分析:多级目录的打印,就是当目录的嵌套。遍历之前,无从知道到底有多少级目录,所以我们还是要使用递归实
现。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| @Test public void test(){ File file = new File("E:"); printDir(file); }
private void printDir(File file) { File[] files = file.listFiles(); if(files!=null){ for (File file1 : files) { if(file1.isFile()) { System.out.println(file1.getName() ); }else{ printDir(file1); } } }
}
|
6. 递归的调用机制图解
6.1 递归能解决的问题
- 各种数学问题: 8 皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google 编程大赛)
- 各种算法中也会使用到递归,比如快排,归并排序,二分查找,分治算法等.
- 将用栈解决的问题–>第归代码比较简洁
6.2 递归需要遵循的重要规则
- 执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
- 方法的局部变量是独立的,不会相互影响, 比如 n 变量
- 如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据.
- 递归 必须向退出递归的条件逼近,否则就是无限递归,出现
StackOverflowError
,死龟了:)
- 当一个方法执行完毕,或者遇到 return,就会返回, 遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕
7. 递归-迷宫问题
7.1 创建地图及测试
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| public class MiGong {
public static void main(String[] args) { int[][] map = new int[8][7]; for (int i = 0; i < map.length; i++) { map[i][0]=1; map[i][6]=1; } for (int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; } map[3][1] = 1; map[3][2] = 1; map[2][2] = 1; map[5][2] = 1; map[5][3] = 1; map[5][4] = 1;
System.out.println("输出地图:"); for (int i = 0; i < map.length; i++) { for (int j = 0; j < map.length-1; j++) { System.out.print(map[i][j]+" "); } System.out.println(); } setWay2(map, 1, 1); System.out.println("找到的路的地图:"); for (int i = 0; i < map.length; i++) { for (int j = 0; j < map.length-1; j++) { System.out.print(map[i][j]+" "); } System.out.println(); }
} }
|
7.2 策略一
策略(方法) 下->右->上->左
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
|
public static boolean setWay(int[][] map,int i,int j) { if(map[6][5]==2) { return true; }else { if(map[i][j] == 0) { 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; } }else { return false; } } }
|
7.3 策略二
策略假定(方法) 上->右->下->左 走
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| public static boolean setWay2(int[][] map,int i,int j) { if(map[6][5]==2) { return true; }else { if(map[i][j] == 0) { map[i][j] = 2; if(setWay2(map, i-1, j)) {
return true; }else if(setWay2(map, i, j+1)) { return true; }else if (setWay2(map, i+1, j)) { return true; }else if (setWay2(map, i, j-1)) { return true; }else { map[i][j] = 3; return false; } }else { return false; } } }
|
8. 递归-八皇后问题
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列、然后判断是否 OK, 如果不 OK,继续放在第二列、第三列、依次把所有列都
放完,找到一个合适
- 继续第三个皇后,还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置,算是找到了一个正确
解
- 当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,
全部得到.
- 然后回头继续第一个皇后放第二列,后面继续循环执行 1,2,3,4 的步骤
8.1 三个方法解决八皇后问题
private boolean judge(int n);
private void print() ;
将皇后摆放的位置输出
private void check(int n);
check 是 每一次递归时,进入到 check 中都有 for(int i = 0; i < max; i++),因此会有回溯
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
|
private boolean judge(int n) { judgeCount++;
for (int i = 0; i < n; i++) { if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n]-array[i])) { return false; } } return true; }
private void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i]+1+" "); } System.out.println(); }
private void check(int n) { if(n == max){ print(); return; } for (int i = 0; i < max; i++) { array[n]= i; if(judge(n)) { check(n+1); } } }
|
8.2 测试
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| public class Queue8 { int max = 8; int[] array = new int[max]; static int count = 0; static int judgeCount = 0;
public static void main(String[] args) { Queue8 queue8 = new Queue8(); queue8.check(0); System.out.println(); System.out.printf("一共有%d解法\n",count); System.out.printf("一共有%d次判断",judgeCount);
} }
|