递归简单来说就是自己调用自己，但是递归一定要有一个出口。否则会不断调用自身导致栈溢出。

调用机制

下边来一个示例代码来看看递归的调用机制

  1.     public static void main(String[] args) {
  2.         //递归简单来讲，就是自己调用自己
  3.         test(4);//先输出2，再然后3，再然后4
  4.     }
  6.     public static void test(int n) {
  7.         //递归必须有一个出口。
  8.         if (n > 2) {
  9.             //再次调用自己。并且 n -1,然后该方法进入阻塞状态。
  10.             //再次调用的方法会在栈中开辟一个新空间。
  11.             test(n - 1);
  12.         }
  13.         System.out.println("n=" + n);//该段代码，debug一下自然会了解
  14.     }

如图：

image.png
每次调用自身的时候，都会在栈中开辟一个新的区域，然后进入到新的区域重新执行代码。原有的的方法会在test(n - 1) 处变为阻塞状态，等待结果的返回，等待结果返回后，往下继续执行代码。

趁热打铁，用递归实现一下阶乘

  1.     public static void main(String[] args) {
  2.         System.out.println(factorial(3)); // 1 * 2 * 3 = 6
  3.     }
  5.     //阶乘问题
  6.     public static int factorial(int n) {
  7.         if (n == 1) {
  8.             return 1;
  9.         } else {
  10.             return factorial(n - 1) * n;
  11.         }
  12.     }

递归用于解决的问题

一些数学问题，球和篮子，8皇后，哈诺塔，阶乘，迷宫等问题。
还可以在一些算法中使用，比如快排，归并排序，二分查找，分治算法等等。
还可以将用栈解决的问题来简单化。

递归必须要知道的事

  • 执行一个方法时，就创建一个新的受保护的独立空间
  • 方法的局部变量事独立的，不会相互影响，如果是引用类型（对象）的话就会一起共享
  • 递归必须向退出递归的条件逼近，否则就是无限递归，死龟了（哈哈哈哈哈哈）
  • 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用就将结果给谁，同时方法

执行完毕或者返回时，该方法也就执行完毕。

递归实例：迷宫问题

小球在迷宫中找路，迷宫用二维数组代替，规定小球从 (1,1) 开始出发 (6,5)为终点
1表示墙，2表示可以通过，3表示这条路走不通, 0表示还没走过。
确定一条走的策略，下->右->上->左,如果该点走不通就再回溯（比如看看这个点的下方向有没有可能到达最终，如果不可能的话，就回来再变换一个方向）。

现在的迷宫地图为
image.png 寻路后的地图应为 —-> image.png

  1.     public static void main(String[] args) {
  2.         //创建一个二维数组用来模拟迷宫的地图。
  3.         int [][] map = new int[8][7];
  4.         //使用1表示墙
  5.         //上下置为1
  6.         for (int i = 0; i < 7; i++) {
  7.             map[0][i] = 1;
  8.             map[7][i] = 1;
  9.         }
  11.         //左右置为1
  12.         for (int i = 0; i < 7; i++) {
  13.             map[i][0] = 1;
  14.             map[i][6] = 1;
  15.         }
  17.         //在第四行做一下挡板
  18.         for (int i = 1; i < 3; i++) {
  19.             map[3][i] = 1;
  20.         }
  23.         //打印一下地图
  24.         for (int i = 0; i < 8; i++) {
  25.             for (int j = 0; j < 7; j++) {
  26.                 System.out.print(map[i][j] + "  ");
  27.             }
  28.             System.out.println();
  29.         }
  30.         setWay(map, 1, 1);
  32.         System.out.println("寻路后的地图：");
  33.         //打印一下地图
  34.         for (int i = 0; i < 8; i++) {
  35.             for (int j = 0; j < 7; j++) {
  36.                 System.out.print(map[i][j] + "  ");
  37.             }
  38.             System.out.println();
  39.         }
  40.     }
  42.     /**
  43.      * 小球找路，规定小球从 (1,1) 开始出发 (6,5)为终点
  44.      * 1表示墙，2表示可以通过，3表示这条路走不通, 0表示还没走过。
  45.      * 确定一条走的策略，下->右->上->左,如果该点走不通就再回溯。
  46.      * @param map 表示地图
  47.      * @param i 从第几行找
  48.      * @param j 从第几列找
  49.      * @return 找到路就返回true，否则返回false
  50.      */
  51.     public static boolean setWay(int[][] map, int i, int j) {
  52.         //map[6][5]代表已经找到通路
  53.         if (map[6][5] == 2) {
  54.             return true;
  55.         } else {
  56.             //判断当前点的情况。如果为0
  57.             if (map[i][j] == 0) {
  58.                 map[i][j] = 2;
  59.                 if (setWay(map, i + 1,j)) {
  60.                     //向下走，如果能走通
  61.                     return true;
  62.                 }else if (setWay(map, i, j + 1)){
  63.                     //向右走
  64.                     return true;
  65.                 }else if (setWay(map, i -1 , j)){
  66.                     //向上走
  67.                     return true;
  68.                 }else if (setWay(map, i, j - 1)){
  69.                     //向左走
  70.                     return true;
  71.                 }else {
  72.                     //如果都走不通的话，变为3
  73.                     map[i][j] = 3;
  74.                     return false;
  75.                 }
  76.             }else {
  77.                 //map[i][j]是其他数字的话，都返回false,不需要我们再走一边。
  78.                 return false;
  79.             }
  80.         }
  82.     }

以上这种地图的排法并没有体现出回溯，如果将map[1][2] = 1,map[2][2] = 1,就会体现出回溯了
image.png ——> image.png

这里简单理解一下回溯就行了，就是试探性的找位置，可以根据树状结构来简单的理解下。
就不贴八皇后代码了，感觉有些抽象。