本文共 5484 字,大约阅读时间需要 18 分钟。
本人是个新手,写下博客用于自我复习、自我总结。 如有错误之处,请各位大佬指出。 学习资料来源于:尚硅谷
递归就是方法自己调用自己。
递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。比如:
//阶乘public static int factorial(int n) { if (n == 1) { return 1; } else { return factorial(n - 1) * n; }}
递归的特点
(1)执行一次方法时,就相当于创建了一个新的受保护的独立空间(栈空间)
(2)方法的局部变量是独立的,不会相互影响 (3)如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据 (4)递归必须向退出递归的条件逼近,否则就是无限递归,出现StackOverflowError。说明:
(1)其实小球得到的路径,和程序员自己设置的找路策略有关。比如:选择“下右上左”和“上右下左”,在某些选择的路径中,肯定是不一样的。如下所示。 (2)也就是说,如果是随机生成的地图,那么因为选择路径策略的不同,也就导致了效率的不同,走过的路径也不同。当然,每一种策略在不同的地图上,总会时高时低,在这里也不过多讨论。package com.guigu.recursion;public class MiGong { // 说明 // 1. map 表示地图 // 2. i,j 表示在地图上的哪个位置 // 3. 如果小球能到迷宫右下角 map[6][5] 位置,则说明通路找到(可以自己调整) // 4. 当map[i][j] 为 0 表示该点没有走过 // 为 1 表示墙 // 为 2 表示通路可以走(从起点到终点的路径) // 为 3 表示该点已经走过,但是走不通 public static void main(String[] args) { // 先创建一个二维数组,模拟迷宫 // 地图 8行7列 int[][] map = new int[8][7]; // 上下全部置为1 for (int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; } // 左右全部置为1 for (int i = 0; i < 8; i++) { map[i][0] = 1; map[i][6] = 1; } // 设置挡板 map[3][2] = 1; map[1][2] = 1; map[2][2] = 1; // 输出地图 System.out.println("原本的地图:"); for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } // 使用递归回溯给小球找路 // 输入的两个数字分别对应起点的横纵坐标 // 默认终点在右下角,即map[6][5] // setWay(map, 1, 1); if(setWay2(map, 1, 1)){ // 输出新的地图 System.out.println("小球走过后的地图:"); for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } }else{ System.out.println("没有通路"); } } // 使用递归回溯来给小球找路 // 下->右->上->左 的策略 /** * @return 如果找到通路,就返回true, 否则返回false */ 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 { // 如果map[i][j] != 0 , 可能是 1, 2, 3 return false; } } } // 上->右->下->左 的策略 /** * @return 如果找到通路,就返回true, 否则返回false */ 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 { // 如果map[i][j] != 0 , 可能是 1, 2, 3 return false; } } }}
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
思路分析:理论上应该创建一个二维数组来表示棋盘,但是实际上可以通过算法,用一个一维数组来解决问题。
比如:arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} arr的下标 表示第几行,即第几个皇后; arr[i] = val , val 表示第i+1个皇后,放在第i+1行的第val+1列这样一来,就发现了一个规律。一维数组中的每一个数代表着某一列,即然不能同列,所以一维数组中的数,一定是 从0到7的 8个数字。同时,一维数组的设定就让每个皇后肯定不同行。所以现在满足了两个条件。现在只需要判断,怎么不在同一斜线上。这个判断方法就是:
设计一个for循环,循环出这个要判断的皇后 之前所有皇后的位置。然后,现在设定a是之前的第a个皇后(即能够不断自加),n是现在这个需要判断的皇后。上面写到,相对于二维数组,下标是行,值是列。看如下的式子:
Math.abs(n-a) == Math.abs(array[n] - array[a]) (abs是求绝对值) n-a 也就意味着两个皇后之间的行差值。 array[n]-array[a] 也就意味着两个皇后之间的列差值。 在同一斜线上的标志: 所以,只要上述判断条件达成,也就意味着某皇后和现在需要判断的皇后,在同一条斜线上。public class Queue8 { //定义一个max:表示共有多少个皇后 int max = 8; //定义数组array, 保存皇后放置位置的结果 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.printf("一共有%d解法", count); System.out.println(); System.out.printf("一共判断冲突的次数%d次", judgeCount); } //编写一个方法,放置第n个皇后 private void check(int n) { if(n == max) { //n = 8 时,证明8个皇后都放好位置 print(); return; } //依次放入皇后,并判断是否冲突 for(int i = 0; i < max; i++) { //先把当前这个皇后 n , 放到该行的第1列 array[n] = i; //判断当放置第n个皇后到i列时,是否冲突 if(judge(n)) { // 不冲突 //接着放下一个皇后,即开始递归 check(n+1); } //如果冲突,就继续执行 array[n] = i; 即将第n个皇后,放置在本行得 后移的一个位置 } } //当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突 private boolean judge(int n) { judgeCount++; for(int a = 0; a < n; a++) { // 说明 //1. array[i] == array[n] 判断第n个皇后是否和前面的皇后在同一列 //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 判断第n个皇后是否和第a个皇后在同一斜线 //3. 判断是否在同一行, 没有必要 if(array[a] == array[n] || Math.abs(n-a) == Math.abs(array[n] - array[a]) ) { return false; } } return true; } //写一个方法,可以将皇后摆放的位置输出 private void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); }}
转载地址:http://tayki.baihongyu.com/