博客

递归：

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

递归调用规则：

1.当程序执行到一个方法时，就会开辟一个独立的空间(栈)

2.每个空间的数据(局部变量)是独立的

可用递归解决部分数学问题：8皇后问题、汉诺塔、阶乘问题、迷宫问题等。还有部分算法中也会用到递归：归并排序、快速排序、分治算法等。

递归需要遵守的重要规则：

1.执行一个方法时，就创建一个新的受保护的独立空间(栈空间)

2.方法的局部变量时独立的，不会相互影响

3.如果方法中使用的是引用类型的变量，就会共享该引用类型的数据

4.递归必须向退出递归的条件逼近，否则就无限循环

5.当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

使用递归回溯解决迷宫问题：

Java代码实现如下：

public class MazeTest {

public static void main(String[] args) {
	// TODO Auto-generated method stub

	//先创建一个二维数组，模拟迷宫
	//地图
	int[][] map = new int[8][7];
	//使用1表示墙
	//上下全部为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][1] = 1;
	map[3][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();
	}
	
	//使用递归回溯给小球找路
	setWay(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();
	}
}

//使用递归回溯来给小球找路
/**
 * 说明：
 * 1.map表示地图
 * 2.i、j表示从地图的哪个位置开始出发(1,1)
 * 3.如果小球能到map(6,6)，则说明通路找到
 * 4.约定：当map[i][j]为0时，表示该点没有走过，为1的代表是墙，
 * 为2表示同路可以走，为3表示该点已经走过，但是走不通
 * 5.在走迷宫时，需要确定一个策略，下->右->上->左，如果该点走不通，再回溯
 */

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;
			}
	}
}

}

根据setWay中找路的策略不同，绘制出的路线也是不同的。