运维开发网

详细介绍了Java的递归算法

运维开发网 https://www.qedev.com 2022-04-24 15:49 出处:网络
Java递归算法是基于Java语言实现的递归算法。递归算法对解决一大类问题很有效,它可以使算法简洁和易于理解。接下来通过本文给大家介绍Java递归算法相关知识,感兴趣的朋友一起学习吧

Java递归算法是基于Java语言实现的递归算法。递归算法对解决一大类问题很有效,它可以使算法简洁和易于理解。接下来通过本文给大家介绍Java递归算法相关知识,感兴趣的朋友一起学习吧


一、介绍


1、介绍

递归:递归是指方法调用自身,每次传入不同的变量。递归帮助程序员解决复杂的问题,同时可以使代码简洁。

迭代和递归的区别:迭代使用循环结构,而递归使用选择结构。递归可以使程序的结构更清晰、更简洁、更容易理解,从而减少阅读代码的时间。它的时间复杂度是递归的次数。

但是大量的递归调用会产生函数的副本,会消耗大量的时间和内存,而迭代不需要这种努力。

递归分为调用阶段和回退阶段,递归的回退顺序是其调用顺序的逆序。

分而治之:当问题规模较大,难以解决时,可以考虑将问题分成几个小模块,逐个解决。


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


二、迷宫问题

问题:找到一条从起点到终点的有效路径。


代码示例:迷宫

public class MiGong { /** * 0:该点没有走过, 1:表示墙, 2:可以走, 3:该点已经走过,但是走不通\ * 策略: 下-gt;右-gt;上-gt;左, 如果该点走不通,再回溯 */ private int[][] map; private int desX; private int desY; /** * 构建 row*col的迷宫 * * @param row 行 * @param col 列 */ public MiGong(int row, int col) { if (row lt;= 0 || col lt;= 0) { return; } map = new int[row][col]; // 默认 上下左右 全部为墙 for (int i = 0; i lt; col; i++) { map[0][i] = 1; map[row - 1][i] = 1; } for (int i = 0; i lt; row; i++) { map[i][0] = 1; map[i][col - 1] = 1; } } /** * 在迷宫内部添加挡板 * * @param i 横坐标 * @param j 纵坐标 */ public void addBaffle(int i, int j) { if (map == null) { return; } // 外面一周都是墙 if (i gt; 0 amp;amp; i lt; map.length - 1 amp;amp; j gt; 0 amp;amp; j lt; map[0].length - 1) { map[i][j] = 1; } } /** * 设置迷宫的终点位置 * * @param desX 横坐标 * @param desY 纵坐标 */ public void setDes(int desX, int desY) { this.desX = desX; this.desY = desY; } public boolean setWay(int i, int j) { // 通路已经找到 if (map[desX][desY] == 2) { return true; } else { if (map[i][j] != 0) { return false; } // map[i][j] == 0 按照策略 下-gt;右-gt;上-gt;左 递归 // 假定该点是可以走通. map[i][j] = 2; if (setWay(i + 1, j)) { return true; } else if (setWay(i, j + 1)) { return true; } else if (setWay(i - 1, j)) { return true; } else if (setWay(i, j - 1)) { return true; } else { // 说明该点是走不通,是死路 map[i][j] = 3; return false; } } } // 显示地图 public void show() { for (int i = 0; i lt; map.length; i++) { for (int j = 0; j lt; map[0].length; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } }}

示例:测试类

// 测试类public class Main { public static void main(String[] args) { MiGong miGong = new MiGong(8, 7); miGong.addBaffle(3, 1); miGong.addBaffle(3, 2); miGong.setDes(6, 5); // 设置目的地 System.out.println("初始地图的情况"); miGong.show(); miGong.setWay(1, 1); // 设置起始位置 System.out.println("小球走过的路径,地图的情况"); miGong.show(); }}

//结果
初图的情况
11111111
100001
100001
110001
100001
10000。球走过的路线,地图


三、八皇后问题

问题:把八个皇后放在一个8×8的棋局中,使它们不能互相攻击,即任意两个皇后不能在同一行、列或对角线上。问有多少种姿势。


代码示例:八皇后

public class Queue8 { private static final int MAX = 8; // 保存皇后放置的位置,比如 arr = {0, 4, 7, 5, 2, 6, 1, 3} private final int[] array = new int[MAX]; public static int count = 0; public static int judgeCount = 0; public void check() { this.check(0); } // check 是每一次递归时,进入到check中都有 for(int i = 0; i lt; max; i++),因此会有回溯 private void check(int n) { // n = 8, 表示8个皇后就已经放好 if (n == MAX) { print(); return; } for (int i = 0; i lt; MAX; i++) { array[n] = i; // 判断当放置第n个皇后到i列时,是否冲突 // 不冲突 if (!judge(n)) { // 接着放n+1个皇后,即开始递归 check(n + 1); } } } private boolean judge(int n) { judgeCount++; for (int i = 0; i lt; n; i++) { // 同一列 或 同一斜线 if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) { return true; } } return false; } private void print() { count++; for (int i = 0; i lt; array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); }}

示例:测试类

// 测试类public class Main { public static void main(String[] args) { Queue8 queue8 = new Queue8(); queue8.check(); System.out.printf("一共有%d解法", Queue8.count); System.out.printf("一共判断冲突的次数%d次", Queue8.judgeCount); // 1.5w }}


四、汉诺塔问题


1、问题



2、思想

如果n = 1,A-gt;C

如果n gt= 2,始终视为两个板块,①底板。②以上所有板块。然后,执行步骤:

(1)先把以上所有板块A-gt;B

(2)将底部托盘A-gt;C

(3)从B-gt转移B塔中的所有塔盘;C


3、代码

例如:河内塔问题

// 汉诺塔public class Hanoitower { // 使用分治算法 public static void move(int num, char a, char b, char c) { // 如果只有一个盘 if (num == 1) { System.out.println("第1个盘从 " + a + "-gt;" + c); } else { // n gt;= 2,总是看做是两个盘,①最下边的盘。②上面所有的盘。则,步骤: // 1.先把上面所有的盘 A-gt;B.移动过程会使用到 c move(num - 1, a, c, b); // 2.把最下边的盘 A-gt;C System.out.println("第" + num + "个盘从 " + a + "-gt;" + c); // 3.把 B 塔的所有盘 从 B-gt;C.移动过程会使用到 a move(num - 1, b, a, c); } }}

示例:测试类

// 测试类public class Main { public static void main(String[] args) { Hanoitower.move(3, 'A', 'B', 'C'); }}

//结果
第一张磁盘从A-gt开始;C
第二个磁盘从A-gt开始;B
第一张盘来自C-gt;B
第三张盘来自A-gt;C
第一张盘来自B-gt;A
第二张盘来自B-gt;C
第一个磁盘从A-gt开始;C


总结

本文到此为止。希望能帮到你,也希望你能多多关注源搜网的更多内容!


0

精彩评论

暂无评论...
验证码 换一张
取 消