递归
简介
程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回，也就是递归必须向退出递归的条件逼近，否则就是死循环，造成StackOverflowError（堆栈溢出错误）。递归，就是在运行的过程中调用自己。
缺点
递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等
案例
阶乘
public static int factorial(int num) { if (num == 1) { return 1; } else { return factorial(num - 1) * num; } }
public static void main(String[] args) { int factorial = factorial(3); System.out.println("factorial = " + factorial); }
当进入到方法factorial时，会开辟一个栈，每次运行到 return factorial(num – 1) * num;都会重新开辟一个栈，当一个方法执行完毕或者遇到return就会将结果返回给调用方，该方法也就执行完毕，结果就是6
迷宫问题
/** * @param map 地图 * @param i 起始位置 * @param j 起始位置 * @return 是否找到路 * * 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 { return false; } } }
int[][] map = new int[8][7]; //1代表墙 for (int i = 0; i < 8; i++) { map[i][0] = 1; map[i][6] = 1; } for (int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; } map[3][1] = 1; map[3][2] = 1; 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(); }
八皇后问题
八皇后问题（英文：Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
回溯算法求解八皇后问题的原则是：有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后是答案。为了加快有无冲突的判断速度，可以给每行和两个方向的每条对角线是否有皇后占据建立标志数组。放下一个新皇后做标志，回溯时挪动一个旧皇后清除标志。
int max = 8; //使用一维数组存放皇后可以拜访的位置，即下标+1行皇后的位置是array[i] int[] array = new int[max]; //记录有多少种方案 static int count; /** * * 找出所有的方案，从第一个皇后放在第一行第一列开始 * 当n=7找到合适位置打印玩方案后，会接着找别的位置，如果都冲突，就会返回到调用它的n=6 * 也就是第七个皇后的第一个合适位置找到以后，会接着循环找别的位置，以此类推，这样就用到了回溯 * * @param n 从哪儿开始 */ public void check (int n) { if (n == max) { print(); count++; return; } for (int i = 0; i < max; i++) { array[n] = i; if (judge(n)) { check(n + 1); } } } /** * array[i] == array[n] 判断这两个皇后是否在同一列 * public static int abs(int a) { * return (a < 0) ? -a : a; * } * Math.abs：也就是求两个数之间的绝对值 * 如果两个皇后处在同一条斜线上，可以把它想象成一个直角三角形 * Math.abs(n - i)就是高 * Math.abs(array[n] - array[i])就是底 * 如果Math.abs(n - i) == Math.abs(array[n] - array[i])就是说明这两个皇后处在同一斜线上 * * @param n 第n个皇后 * @return 是否冲突 */ //判断新皇后的位置是否与之前的存在冲突 private boolean judge (int n) { for (int i = 0; i < n; i++) { if (array[i] == array[n] ||Math.abs(n - i) == Math.abs(array[n] - array[i])) { return false; } } return true; } //打印 public void print() { for (int item : array) { System.out.print(item + " "); } System.out.println(); }
Queue queue = new Queue(); queue.check(0); System.out.println("count = " + count);