递归

一、递归概述

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

二、递归的调用机制

1. 当程序执行到一个方法时，就会开辟一个独立的空间（栈）
2. 每个空间的数据（局部变量）都是独立的

三、递归解决的问题

1. 各种数学问题如：8 皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题（google 编程大赛）
2. 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等
3. 将用栈解决的问题 --> 递归代码比较简洁

四、递归的原则

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

五、迷宫问题

package work.rexhao.recursion;

import java.util.Scanner;

public class mazeDemo {

	static int size;
	static String[] map;
	static int ans = 0;
	static boolean[][] flag;

	public static void main(String[] args) {
		System.out.println("输入地图的大小:");
		Scanner sc = new Scanner(System.in);
		size = Integer.parseInt(sc.nextLine());
		System.out.println("输入地图:");
		map = new String[size];
		flag = new boolean[size][size];
		for (int i = 0; i < size; i++) {
			map[i] = sc.nextLine();
		}
		int x = 0, y = 0;
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (map[i].charAt(j) == 'B') {
					x = i;
					y = j;
				}
			}
		}
		maze(x, y);
		System.out.println(ans);
		sc.close();
	}

	public static void maze(int x, int y) {
		if (check(x, y) && map[x].charAt(y) == 'E') {
			ans++;
			return;
		}
		flag[x][y] = true;
		if (check(x + 1, y)) {
			maze(x + 1, y);
		}
		if (check(x - 1, y)) {
			maze(x - 1, y);
		}
		if (check(x, y + 1)) {
			maze(x, y + 1);
		}
		if (check(x, y - 1)) {
			maze(x, y - 1);
		}
		flag[x][y] = false;
	}

	public static boolean check(int x, int y) {
		if (x >= size || y >= size || x < 0 || y < 0) {
			return false;
		} else
			return (map[x].charAt(y) == '.' || map[x].charAt(y) == 'E') && !flag[x][y];
	}
}

六、回溯算法（八皇后问题）

1、八皇后问题介绍

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯 • 贝瑟尔于1848 年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法(92)。

2、思路分析

1. 相同剪枝：如果在同一行/列，舍弃
2. 斜向剪枝：对于y=x方向，行+列为定值；对于y=-x方向，行-列为定值

3、代码实现

package work.rexhao.recursion;

public class queueEight {
	public static int[] chess = new int[8];
	public static int ans = 0;
	public static int[] x1; // 对角线1
	public static int[] x2; // 对角线2

	public static void main(String[] args) {
		queue(chess, 0);
		System.out.println(ans);
	}

	public static void queue(int[] chess, int times) {
		/*
		 * 退出条件
		 */
		if (times == 8) {
			/*
			 * 重复
			 */
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j < 8; j++) {
					if(i == j) continue;
					if (chess[i] == chess[j]) {
						return;
					}
				}
			}
			/*
			 * 对角线
			 */
			x1 = new int[20];
			x2 = new int[20];
			for (int i = 0; i < 8; i++) {
				x1[chess[i] - i + 8]++;
				x2[i + chess[i]]++;
			}
			for (int i = 0; i < 20; i++) {
				if (x1[i] > 1 || x2[i] > 1) {
					return;
				}
			}
			for(int i: chess) {
				System.out.print(i + " ");
			}
			System.out.println();
			ans++;
			return;
		}

		/*
		 * 递归
		 */
		for (int i = 1; i < 9; i++) {
			chess[times] = i;
			queue(chess, times + 1);
		}

	}
}