递归

1、定义
所谓递归就是自己调用自己。

2、分类
递归分为两种:

直接递归:方法自身调用自己。
间接递归:A方法调用B方法,B方法调用C方法,C方法再调用A方法。
3、注意事项
递归一定要有条件限定,保证递归能够停止下来,否则会形成死循环并发生栈内存溢出(StackOverflowError)。
递归中虽然限定了停止下来的条件,但是递归次数不能太多,否则也会发生栈内存溢出。
禁止构造方法递归。

递归的例子

八皇后问题

八皇后问题分析

八皇后是一个小游戏,在古代有多位数学家解过这个问题,但是都没有最终的答案,现代计算机经过计算得出八皇后问题的解法总共有92种

递归解法

创建一个一位数组作为棋盘,为什么一维数组都能当做棋盘呢,用到一个技巧,将一维数组的下标当做棋盘的行,值当做一位数组的列,所以在放置棋子的时候只需要循环放置就能将每一个颗棋子放在不同的行

首先将第一个棋子放在第一行的第一列,然后放置第二颗棋子在第二行的第一列,放置之前需要和前面的棋子进行检查,符合结果的棋子才能放置,后面的棋子也是如此,每一次都是从第一颗棋子开始放置,直到最后一颗棋子放置完毕,这样就得到一个结果,将结果打印输出

放置完最后一颗棋子之后开始回溯,回溯:将最后一颗棋子移动不同的位置看看是否存在其他解法,如果没有回退到倒数第二颗,移动一个位置然后在到最后一颗再移,再回退,再移,重复…(大概一万五千多步)直到位于第一行的棋子位于第八列为止,这样就找出了所有的可能

代码实现

package cn.rlfit.eightQueen;

public class EightQueen {
/*递归解决八皇后问题
 * 1. 建立一个一维数组存储每一个结果的值
 * 2. 遍历方法
 * 3. 放置方法
 */
	public static void main(String[] args) {
		Queen queen = new Queen(8);
		queen.check(0);
	}
}
class Queen{
	int max = 0;
	int[] array;
	public Queen(int max) {
		this.max = max;
		array = new int[max];
	}
//	打印
	public void print(int[] array) {
		for (int i : array) {
			System.out.print(" "+i);
		}
		System.out.println();
	}
//	放置第n个皇后的时候和前面的皇后比较
	public boolean isOk(int n) {
		for (int i = 0; i < n; i++) {
			if (array[n] == array[i] || Math.abs(n-i) == Math.abs(array[i] - array[n])) {
//				条件成立说明在同一列或者对角线
				return false;
			}
		}
		return true;
	}
//	开始放置皇后
	public void check(int n) {
		if (n == max) {
			print(array);
			return;
		}
		for (int i = 0; i < max; i++) {
			array[n] =  i;
			if(isOk(n)) {
				check(n + 1);
			}
		}
	}
}