递归的概念以及迷宫问题
2023-03-31 10:45:44 时间
1、概念
递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。并且递归用到了虚拟机栈
2、能解决的问题
数学问题
- 八皇后问题
- 汉诺塔
- 求阶乘
- 迷宫问题
- 球和篮子
各种排序算法
3、规则
-
方法的变量是独立的,不会相互影响的
-
如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据
-
递归必须向退出递归的条件逼近,否则就是无限递归,出现 StackOverflowError
-
当一个方法执行完毕,或者遇到 return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或
者返回时,该方法也就执行完毕
4、迷宫问题
思路
- 用一个二维矩阵代表地图
- 1代表边界
- 0代表未做过该地点
- 2代表走过且能走得通
- 3代表走过但走不通
- 设置起点和终点以及每个地点的行走策略
- 行走策略指在该点所走的方向的顺序,如 下->右->上->左(调用寻找路径的方法,使用递归)
- 每次行走时假设该点能够走通,然后按照策略去判断,如果所有策略判断后都走不通,则该点走不通
图解
初始地图,假设圆点为终点
如以下->右->上->左的策略,路线如下
代码
public class MiGong { //用0表示没有走过的路,用1表示墙 public static void main(String[] args) { int[][] map = new int[8][7];//创建地图 //设置地图的墙体,用1来表示 for (int i = 0; i < 7; i++){ map[0][i] = 1; map[7][i] = 1; } for (int i = 0; i < 8; i++){ map[i][0] = 1; map[i][6] = 1; } map[3][1] = 1; map[3][2] = 1; System.out.println("迷宫地图:"); for (int i = 0; i < map.length; i++){ for (int j = 0; j < map[0].length; j++){ System.out.print(map[i][j]+" "); } System.out.println(); } setWay(map,1,1); System.out.println("启动走迷宫后:"); for (int i = 0; i < map.length; i++){ for (int j = 0; j < map[0].length; j++){ System.out.print(map[i][j]+" "); } System.out.println(); } } /** * 用2表示走过的路,用3表示走过且不能继续走下去的路 * @param map 表示地图 * @param i 表示第i行开始找 * @param j 表示第j列开始找 * @return 返回true的时候表示可以走,返回false的时候表示不能走 */ public static boolean setWay(int[][] map, int i, int j){ if (map[6][5] == 2){//设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 {//非0的情况可能是1、2、3,直接false return false; } } } }
结果:
相关文章
- 硅谷科技巨头最刁钻面试题集锦
- 免费IDE编辑器才是Java程序员的最爱
- 程序员分享接私活心得 晒晒私活成果
- 现实总是很残酷:这样的情况想不辞职都难!
- 基于Java实现批量下载网络图片
- 命令行的艺术
- 码农、黑客和2B程序员之间的区别
- 在什么情况下,Java比C++慢很多?
- 深度解读ASP.NET 5 & MVC6
- Java程序员新手老手都离不开八大开发工具
- 哪些因素影响Java调用的性能?
- JFinal 2.0 发布,JAVA 极速 WEB+ORM 框架
- Go 摆脱了 C,又惹上了 Java?
- 让你的 PHP 7 更快 (GCC PGO)
- Java 8默认方法会破坏你的(用户的)代码
- 我要阻止做java开发的男朋友去创业型公司工作吗?
- 8个超实用的Java测试工具和框架
- 十个精妙的Java编码最佳实践
- 几个面试经典算法题Java解答
- Java 9许愿清单:请赐予我们更理想的垃圾回收机制