请选择 进入手机版 | 继续访问电脑版

[java] Java的递归算法详解

[复制链接]
查看29 | 回复4 | 2021-9-12 20:07:06 | 显示全部楼层 |阅读模式
目次

一、先容

1、先容

递归:递归就是方法本身 调用本身 ,每次调用时传入不同的变量。递归有助于编程者办理 复杂的标题 ,同时可以让代码变得简洁。

迭代和递归区别:迭代使用 的是循环布局 ,递归使用 的选择布局 。使用 递归能使程序的布局 更清晰 、更简洁、更容易 让人明白 ,从而减少读懂代码的时间。当时 间复杂度就是递归的次数。

但大量的递归调用会建立函数的副本,会斲丧 大量的时间和内存,而迭代则不必要 此种付出。

递归函数分为调用和回退阶段,递归的回退次序 是它调用次序 的逆序。

分治:当一个标题 规模较大且不易求解的时间 ,就可以思量 将标题 分成几个小的模块,逐一办理 。

2、案例

  • 兔子繁殖的标题 。(斐波那契数列)。
  • 计算 n! 。
  • 恣意 长度的字符串反向输出。
  • 折半查找算法的递归实现。
  • 汉诺塔标题
  • 八皇后标题

二、迷宫标题

标题 :探求 一条从起始点到达止境 的有用 路径。

Java的递归算法详解

代码示例:迷宫

  1. public class MiGong {
  2. /**
  3. * 0:该点没有走过, 1:表示墙, 2:可以走, 3:该点已经走过,但是走不通\
  4. * 策略: 下->右->上->左, 如果该点走不通,再回溯
  5. */
  6. private int[][] map;
  7. private int desX;
  8. private int desY;
  9. /**
  10. * 构建 row*col的迷宫
  11. *
  12. * @param row 行
  13. * @param col 列
  14. */
  15. public MiGong(int row, int col) {
  16. if (row <= 0 || col <= 0) {
  17. return;
  18. }
  19. map = new int[row][col];
  20. // 默认 上下左右 全部为墙
  21. for (int i = 0; i < col; i++) {
  22. map[0][i] = 1;
  23. map[row - 1][i] = 1;
  24. }
  25. for (int i = 0; i < row; i++) {
  26. map[i][0] = 1;
  27. map[i][col - 1] = 1;
  28. }
  29. }
  30. /**
  31. * 在迷宫内部添加挡板
  32. *
  33. * @param i 横坐标
  34. * @param j 纵坐标
  35. */
  36. public void addBaffle(int i, int j) {
  37. if (map == null) {
  38. return;
  39. }
  40. // 外面一周都是墙
  41. if (i > 0 && i < map.length - 1 && j > 0 && j < map[0].length - 1) {
  42. map[i][j] = 1;
  43. }
  44. }
  45. /**
  46. * 设置迷宫的终点位置
  47. *
  48. * @param desX 横坐标
  49. * @param desY 纵坐标
  50. */
  51. public void setDes(int desX, int desY) {
  52. this.desX = desX;
  53. this.desY = desY;
  54. }
  55. public boolean setWay(int i, int j) {
  56. // 通路已经找到
  57. if (map[desX][desY] == 2) {
  58. return true;
  59. } else {
  60. if (map[i][j] != 0) {
  61. return false;
  62. }
  63. // map[i][j] == 0 按照策略 下->右->上->左 递归
  64. // 假定该点是可以走通.
  65. map[i][j] = 2;
  66. if (setWay(i + 1, j)) {
  67. return true;
  68. } else if (setWay(i, j + 1)) {
  69. return true;
  70. } else if (setWay(i - 1, j)) {
  71. return true;
  72. } else if (setWay(i, j - 1)) {
  73. return true;
  74. } else {
  75. // 说明该点是走不通,是死路
  76. map[i][j] = 3;
  77. return false;
  78. }
  79. }
  80. }
  81. // 显示地图
  82. public void show() {
  83. for (int i = 0; i < map.length; i++) {
  84. for (int j = 0; j < map[0].length; j++) {
  85. System.out.print(map[i][j] + " ");
  86. }
  87. System.out.println();
  88. }
  89. }
  90. }
复制代码

  代码示例:测试类

  1. // 测试类
  2. public class Main {
  3. public static void main(String[] args) {
  4. MiGong miGong = new MiGong(8, 7);
  5. miGong.addBaffle(3, 1);
  6. miGong.addBaffle(3, 2);
  7. miGong.setDes(6, 5); // 设置目的地
  8. System.out.println("初始地图的情况");
  9. miGong.show();
  10. miGong.setWay(1, 1); // 设置起始位置
  11. System.out.println("小球走过的路径,地图的情况");
  12. miGong.show();
  13. }
  14. }
复制代码
  1. // 结果
  2. 初始地图的情况
  3. 1 1 1 1 1 1 1
  4. 1 0 0 0 0 0 1
  5. 1 0 0 0 0 0 1
  6. 1 1 1 0 0 0 1
  7. 1 0 0 0 0 0 1
  8. 1 0 0 0 0 0 1
  9. 1 0 0 0 0 0 1
  10. 1 1 1 1 1 1 1
  11. 小球走过的路径,地图的情况
  12. 1 1 1 1 1 1 1
  13. 1 2 0 0 0 0 1
  14. 1 2 2 2 0 0 1
  15. 1 1 1 2 0 0 1
  16. 1 0 0 2 0 0 1
  17. 1 0 0 2 0 0 1
  18. 1 0 0 2 2 2 1
  19. 1 1 1 1 1 1 1
复制代码

三、八皇后标题

标题 :在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:恣意 两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

Java的递归算法详解

代码示例:八皇后

  1. public class Queue8 {
  2. private static final int MAX = 8;
  3. // 保存皇后放置的位置,比如 arr = {0, 4, 7, 5, 2, 6, 1, 3}
  4. private final int[] array = new int[MAX];
  5. public static int count = 0;
  6. public static int judgeCount = 0;
  7. public void check() {
  8. this.check(0);
  9. }
  10. // check 是每一次递归时,进入到check中都有 for(int i = 0; i < max; i++),因此会有回溯
  11. private void check(int n) {
  12. // n = 8, 表示8个皇后就已经放好
  13. if (n == MAX) {
  14. print();
  15. return;
  16. }
  17. for (int i = 0; i < MAX; i++) {
  18. array[n] = i;
  19. // 判断当放置第n个皇后到i列时,是否冲突
  20. // 不冲突
  21. if (!judge(n)) {
  22. // 接着放n+1个皇后,即开始递归
  23. check(n + 1);
  24. }
  25. }
  26. }
  27. private boolean judge(int n) {
  28. judgeCount++;
  29. for (int i = 0; i < n; i++) {
  30. // 同一列 或 同一斜线
  31. if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
  32. return true;
  33. }
  34. }
  35. return false;
  36. }
  37. private void print() {
  38. count++;
  39. for (int i = 0; i < array.length; i++) {
  40. System.out.print(array[i] + " ");
  41. }
  42. System.out.println();
  43. }
  44. }
复制代码

代码示例:测试类

  1. // 测试类
  2. public class Main {
  3. public static void main(String[] args) {
  4. Queue8 queue8 = new Queue8();
  5. queue8.check();
  6. System.out.printf("一共有%d解法", Queue8.count);
  7. System.out.printf("一共判断冲突的次数%d次", Queue8.judgeCount); // 1.5w
  8. }
  9. }
复制代码

四、汉诺塔标题

1、标题

Java的递归算法详解

2、头脑

假如 n = 1,A -> C

假如 n >= 2,总是看做是两个盘,①最下边的盘。②上面全部 的盘。则,步骤:

(1)先把上面全部 的盘 A->B

(2)把最下边的盘 A->C

(3)把 B 塔的全部 盘 从 B->C

3、代码

代码示例:汉诺塔标题

  1. // 汉诺塔
  2. public class Hanoitower {
  3. // 使用分治算法
  4. public static void move(int num, char a, char b, char c) {
  5. // 如果只有一个盘
  6. if (num == 1) {
  7. System.out.println("第1个盘从 " + a + "->" + c);
  8. } else {
  9. // n >= 2,总是看做是两个盘,①最下边的盘。②上面所有的盘。则,步骤:
  10. // 1.先把上面所有的盘 A->B.移动过程会使用到 c
  11. move(num - 1, a, c, b);
  12. // 2.把最下边的盘 A->C
  13. System.out.println("第" + num + "个盘从 " + a + "->" + c);
  14. // 3.把 B 塔的所有盘 从 B->C.移动过程会使用到 a
  15. move(num - 1, b, a, c);
  16. }
  17. }
  18. }
复制代码

代码示例:测试类

  1. // 测试类
  2. public class Main {
  3. public static void main(String[] args) {
  4. Hanoitower.move(3, 'A', 'B', 'C');
  5. }
  6. }
复制代码
  1. // 结果
  2. 第1个盘从 A->C
  3. 第2个盘从 A->B
  4. 第1个盘从 C->B
  5. 第3个盘从 A->C
  6. 第1个盘从 B->A
  7. 第2个盘从 B->C
  8. 第1个盘从 A->C
复制代码

总结

本篇文章就到这里了,盼望 可以或许 给你带来帮助,也盼望 您可以或许 多多关注脚本之家的更多内容!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar 压后牙 | 2021-9-13 00:52:23 | 显示全部楼层
看帖不回帖都是耍流氓!
回复

使用道具 举报

avatar hhhong2017 | 2021-9-27 02:08:42 | 显示全部楼层
admin楼主会死的很有节奏的!
回复

使用道具 举报

avatar 真好210 | 2021-10-15 23:32:19 | 显示全部楼层
勤奋灌水,天天向上!
回复

使用道具 举报

avatar 15254714558 | 昨天 06:48 | 显示全部楼层
好东西,学习学习!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则