算法(Java实现)-详谈递归(迷宫回溯问题)


1、递归的概念

简单的说: 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题, 同时可以让代码变得简洁。

2、递归调用的机制
(1)打印问题

看下面代码:

public class RecursionTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
//通过打印问题,回顾递归调用机制
test(4);
}
//打印问题.
public static void test(int n) {
if (n > 2) {
test(n - 1);
}
System.out.println("n=" + n);
}
}

n=2
n=3
n=4

分析JVM内部运行机制:
算法(Java实现)-详谈递归(迷宫回溯问题)
一开始,最先运行主方法,在栈内开辟空间而后执行test(4)重新开一段栈内空间,当程序执行到一个方法时,就会开辟一个独立的空间(栈),直到n=2,这时不再执行if语句里面的test方法也就不再开辟独立的空间,这时就开始执行if语句外面的System.out.println(“n=” + n);语句,打印n=2,执行完后这个空间被垃圾回收机制回收,然后执行n=3的test方法中的System.out.println(“n=” + n);语句,打印n=3,依次回归执行,直到最后退出程序算法(Java实现)-详谈递归(迷宫回溯问题)算法(Java实现)-详谈递归(迷宫回溯问题)
改一下:

public class RecursionTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
//通过打印问题,回顾递归调用机制
test(4);
}
//打印问题.
public static void test(int n) {
if (n > 2) {
test(n - 1);
} else {
System.out.println("n=" + n);
}
}
}

n=2

分析:只有最上面的n=2的栈没有进入if语句中而是进了else语句中,所以打印了n=2,而后面的3和4进入了if语句中就不会再执行else中的打印语句。

(2)阶乘问题

public class RecursionTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
//通过打印问题,回顾递归调用机制
int res = factorial(3);
System.out.println("res=" + res);
}
//阶乘问题
public static int factorial(int n) {
if (n == 1) {
return 1;
} else {
return factorial(n - 1) * n; // 1 * 2 * 3
}
}
}

res=6

执行过程:

    factorial(3 - 1) * 3 ——> factorial(2) * 3
    factorial(2 - 1) * 2*3 ——> factorial(1) * 2 *3
    1 * 2 * 3 ——> 6

递归遵循的规则:

    执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
    方法的局部变量是独立的,不会相互影响
    如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据.
    递归必须向退出递归的条件逼近,否则就是无限递归,出现StackOverflowError,死龟了:)
    当一个方法执行完毕,或者遇到return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕。

3、迷宫回溯问题

以一个M×N的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计程序,对任意设定的迷宫,求出从入口到出口的所有通路。
  下面我们来详细讲一下迷宫问题的回溯算法。
(入口) 0 0 1 0 0 0 1 0
   0 0 1 0 0 0 1 0
   0 0 1 0 1 1 0 1
   0 1 1 1 0 0 1 0
   0 0 0 1 0 0 0 0
   0 1 0 0 0 1 0 1
   0 1 1 1 1 0 0 1
   1 1 0 0 0 1 0 1
   1 1 0 0 0 0 0 0(出口)
  该图是一个迷宫的图。1代表是墙不能走,0是可以走的路线。只能往上下左右走,直到从左上角到右下角出口。
  做法是用一个二维数组来定义迷宫的初始状态,然后从左上角开始,不停的去试探所有可行的路线,碰到1就结束本次路径,然后探索其他的方向,当然我们要标记一下已经走的路线,不能反复的在两个可行的格子之间来回走。直到走到出口为止,算找到了一个正确路径。

import java.util.Scanner;
public class MiGong2 {
public static void main(String[] args) {
int maxRow,maxLine;
Scanner scanner = new Scanner(System.in);
// 获取行
System.out.println("请输入行数:");
maxRow = scanner.nextInt();
// 获取列
System.out.println("请输入列数:");
maxLine = scanner.nextInt();
System.out.println("请输入地图:");
//输入地图
int [][] array = new int [maxRow][maxLine];
for(int i = 0; i < maxRow; i++){
for(int j = 0; j < maxLine; j++){
array[i][j] = scanner.nextInt();
}
}
//记录起始时间
Long start = System.currentTimeMillis();
//找出路
new MiGong2().check(0, 0, array, maxRow, maxLine);
//记录结束时间
Long end = System.currentTimeMillis();
System.out.println("耗时:" + (end-start) + "ms");
}
/**
* 制定走的规则
* @param i
* @param j
* @param array
* @param maxRow
* @param maxLine
*/
private void check(int i, int j, int[][] array, int maxRow, int maxLine) {
// 递归出口(如果到达右下角出口)
if (i == maxRow - 1 && j == maxLine - 1) {
print(array, maxRow, maxLine);
return;
}
//向右走
if (canMove(i, j, i, j + 1, array, maxRow, maxLine)) {
// 已走过的点置标志位5
array[i][j] = 5;
// 从下一个点继续寻路
check(i, j + 1, array, maxRow, maxLine);
// 均不可行,则恢复现场
array[i][j] = 0;
}
//向左走
if (canMove(i, j, i, j - 1, array, maxRow, maxLine)) {
// 标记为已走
array[i][j] = 5;
// 递归调用
check(i, j - 1, array, maxRow, maxLine);
array[i][j] = 0;
}
//向下走
if (canMove(i, j, i + 1, j, array, maxRow, maxLine)) {
array[i][j] = 5;
check(i + 1, j, array, maxRow, maxLine);
array[i][j] = 0;
}
//向上走
if (canMove(i, j, i - 1, j, array, maxRow, maxLine)) {
array[i][j] = 5;
check(i - 1, j, array,maxRow, maxLine);
array[i][j] = 0;
}
}
/**
* 判断[i,j]-->[targetI,targetJ]是否可行
* @param i
* @param j
* @param targetI
* @param targetJ
* @param array
* @param maxRow
* @param maxLine
* @return boolean 可否通过
*/
private boolean canMove(int i, int j, int targetI, int targetJ, int[][] array, int maxRow, int maxLine) {
// System.out.println("从第" + (i + 1) + "行第" + (j + 1) + "列,走到第" + (targetI + 1) + "行第" + (targetJ + 1) + "列");
if (targetI < 0 || targetJ < 0 || targetI >= maxRow || targetJ >= maxLine) {
// System.out.println("到达最左边或最右边,失败了");
return false;
}
if (array[targetI][targetJ] == 1) {
// System.out.println("目标是墙,失败了");
return false;
}
//避免在两个空格间来回走
if (array[targetI][targetJ] == 5) {
// System.out.println("来回走,失败了");
return false;
}

return true;
}
/**
* 打印可行路径
* @param array
* @param maxRow
* @param maxLine
*/
private void print(int [][] array, int maxRow, int maxLine) {
System.out.println("得到一个解:");
for (int i = 0; i < maxRow; i++) {
for (int j = 0; j < maxLine; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println();
}
}
}

请输入行数:
9
请输入列数:
8
请输入地图:
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
得到一个解:
5 5 1 0 0 0 1 0
5 5 1 0 0 0 1 0
5 0 1 0 1 1 0 1
5 1 1 1 0 0 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解:
5 5 1 0 0 0 1 0
5 5 1 0 0 0 1 0
5 0 1 0 1 1 0 1
5 1 1 1 5 5 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解:
5 5 1 0 0 0 1 0
0 5 1 0 0 0 1 0
5 5 1 0 1 1 0 1
5 1 1 1 0 0 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解:
5 5 1 0 0 0 1 0
0 5 1 0 0 0 1 0
5 5 1 0 1 1 0 1
5 1 1 1 5 5 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解:
5 0 1 0 0 0 1 0
5 5 1 0 0 0 1 0
5 5 1 0 1 1 0 1
5 1 1 1 0 0 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解:
5 0 1 0 0 0 1 0
5 5 1 0 0 0 1 0
5 5 1 0 1 1 0 1
5 1 1 1 5 5 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解:
5 0 1 0 0 0 1 0
5 0 1 0 0 0 1 0
5 0 1 0 1 1 0 1
5 1 1 1 0 0 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解:
5 0 1 0 0 0 1 0
5 0 1 0 0 0 1 0
5 0 1 0 1 1 0 1
5 1 1 1 5 5 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
耗时:5ms

欢迎持续关注!
个人博客站:jQueryZK Blog

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

算法(Java实现)-详谈递归(迷宫回溯问题)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 算法(Java实现)-详谈递归(迷宫回溯问题)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏