一、递归-回溯算法
1.递归的思想
递归就是方法自己调用自己，每次调用的时候传入不同的变量
2.递归的原理
1）每执行一个方法，就在【栈内存】中分配一块空间，该空间是独立的。
2）如果是【基本数据类型】，则每块空间中的变量都是局部变量，是相互【独立】的
3）如果是【引用数据类型】，则每块空间中的变量是【共享】的，因为存的是地址值，new出来的对象都存放在【堆内存】中并分配一个【地址值】，方法执行的时候，会根据栈空间中保存的变量地址值，在堆内存中找到同一个变量，因为地址值指向的都是同一个。
4）每次递归后，条件要【不断收敛】，即必须要保证能退出递归，否则递归就无法结束，会不断在栈内存中分配空间，造成【栈溢出】（StackOverFlow）问题。
二、排列问题
1.排列公式
A_n_m = n*(n-1)*(n-2)*...*(n-m+1)=n!/(n-m)!
2.以A_4_4 = 432*1=4！为例：
1）准备工作
1）创建一个集合prelist：[1,2,3,4]
2）创建一个存储排列结果的集合preList
3）定义一个从preList中遍历取元素，然后添加元素到preList集合中的方法：setNum
2）递归调用setNum方法，在方法内部包括：
1）递归结束的条件：向preList集合中添加4个数，就结束递归，并打印结果
2）判断过程
【遍历】preList集合，取出preList集合中的第一个元素，如果resList集合中没有该元素，就添加到resList集合；
否则，继续取出preList集合第二个元素，依次类推，直到元素可以添加到resList集合中。
3）如果经过判断，某个元素添加成功了，则【递归】调用setNum方法，继续添加下一个元素
3）回溯
当成功找到【第一种解法】 [1,2,3,4]时,就【回退】到上一个栈，此时，【栈顶】元素为3，还可以试一下4，所以又将栈顶元素设为4，然后再【递归】设置最后一个数，显然，只能是3。所以，【第二种解法】是[1,2,4,3]。
当找到第二种解法后，在【回退】到上一个栈，因为数字只能设置为3或4，所以没有其他选择了，【继续回退】到上一个栈，当前数字是2，还可以选择3或4，所以先设置为3，然后【递归】设置其他数；在设置为4，递归设置其他数。
到最后，resList集合中【第一个元素为1的排列结果就都找到了】。
然后再将2设置为resList的一个元素，就能将2开头的所有排列结果找到，以此类推，找到以3开头的，以4开头的。
4）最终结果打印的顺序就是上面分析的顺序，即：
[1,2,3,4]
[1,2,4,3]
[1,3,2,4]
[1,3,4,2]
5）注意：回退到上一个栈时，之所以能试一试其他的数，是因为每次递归的时候，都【遍历】了prelist数组。
3.Java代码
public class Permutation {
static Stack<Integer> stack = new Stack<>();
public static void main(String[] args) {
int res = permutation(4, 3);
System.out.println("A_4_3的结果为：" + res);
List<Integer> preList = new ArrayList<>();
preList.add(1);
preList.add(2);
preList.add(3);
preList.add(4);
System.out.println("preList=" + preList);
enumerration(preList, 4, 0);
}
/**
* 全排列公式实现
* @param n 一共有n个
* @param m 从n中取m个
* @return 表示一共有多少种取法
*/
public static int permutation(int n, int m){
int res = 1;
/*
A_4_2 = 4 * 3 循环两次实现：4*1*3
A_4_3 = 4 * 3 * 2 循环三次实现：4*1*3*2
A_n_m 需要循环m次实现：n*1*(n-1)*...*(n-m+1)
*/
for (int i = 0; i < m; i++) {
res *= n;
n--;
}
return res;
}
/**
* 列举出排列结果
* 例如A_4_4,排列结果就是在给的四个数中依次不重复地选择一个数
* @param preList 存放需要排列的数据的列表
* @param total 表示一共选几次数
* @param cur 表示当前是第几次选数
*/
public static void enumerration(List<Integer> preList, int total, int cur){
if (cur == total){
System.out.println(stack);
return;
}
for (Integer item : preList) {
if (!stack.contains(item)){
stack.push(item);
enumerration(preList, total, cur+1);
stack.pop();
}
}
}
}
三、八皇后问题
1.问题描述
任意两个皇后不能处于同一行、同一列或同一斜线上，问有多少种摆法？
跟据稀疏数组的思想，我们把二维数组表示的棋盘压缩成一维数组。
arr[i]=value。i表示第i+1个皇后，value表示这个皇后应该放在第i+1行的第i+1列。
2.思路分析
1）与排列问题类似，先将第一个皇后放在第一行，第一列，然后递归调用放置皇后的方法，直到产生第一个正确解法
2）当产生第一个正确解法后，回退到上一个栈（即倒数第二行），试一下其他的位置，再调用放置皇后的方法，设置最后一行的皇后，依次类推，最终找到了第一个皇后放在第一行第一列的所有正确解
3）然后再将第一个皇后放在第一行第二列，。。。
3.Java代码
在这里插入代码片
