【数据结构与算法】（JAVA版）递归，迷宫问题的解决

递归

递归需要遵守的规则：

1)执行一个方法时，就在JVM栈中开辟一块内存，用于存放执行方法时所需的数据，比如方法局部变量，对象引用等，这块内存叫栈帧。JVM栈是JVM运行时内存的一个区域，JVM运行时内存还包括堆、方法区、程序计数器等区域
2)方法的局部变量是独立的，不会相互影响
3)如果方法中使用的是引用类型的变量（比如数组）,就会共享该引用类型的数据
4)当一个方法执行完毕，或者遇到return, 就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。
5)递归必须向退出递归的条件逼近，否则就是无限递归出现StackOverflow
6)抛出StackOverflow的原因
    如果递归方法中没有终止条件，递归调用将不停的在栈中创建栈帧，如果超过虚拟机规定的栈最大容量则报StackOverflowError错误

1.递归调用必须要有终止条件（出口）

2.递归调用每次都要缩小范围，才能达到终止条件

例：求一个数据区间的累加和

public class Test {
	public static void main(String[] args) {
        int x = test(1,3);
		System.out.println(x);
	}
	public static int test(int start,int end) {
        //递归方法的出口
		if(start == end) {
			return end;
		}
		return start + test(start+1,end);
	}
}

图文说明：

迷宫问题

package dataStructure;
public class Labyrint {
	public static void main(String[] args) {
		int[][] map = new int[8][7];
		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;
		for(int[] array:map) {
			for(int i:array) {
				System.out.print(i+"  ");
			}
			System.out.println();
		}
		setWay(map,1,1);
		System.out.println("探测之后的路线");
		for(int[] array:map) {
			for(int i:array) {
				System.out.print(i+"  ");
			}
			System.out.println();
		}
	}
	/**
	 * 使用递归回溯来找路
	 * map表示地图
	 * i,j表示初始位置所在行，列
	 * 如果小球能到map[6][5]位置，则说明通路找到
	 * 约定：当map[x][y] 为0表示该点没有走过，1表示墙，2表示通路可以走，3表示已经探测过但是走不通
	 * 策略：按照 下右上左 的顺序进行探测，如果走不通，再回溯
	 * 
	 * */
	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;
			}
		}
	}
}