数据结构与算法——递归回溯

简单来说，递归就是方法自己调用自己。有点类似于从底层开始一步一步地往上归纳。

每次调用时必须传入不同的变量，用该变量来判断作为最后退出的条件，否则递归将无限执行下去直到栈内存溢出。

两个简单的小例子

打印问题举例：

递归的常用场景

递归的使用规则

我的理解：其实在逻辑上就是调用的方法里还有方法，然后方法里还有方法……只不过，当每一层里的方法都是自己时，就称之为递归。

---

递归实现迷宫问题

先写一个迷宫

递归回溯

此时可以求出最短路径，虽然没有学过类似的算法，但是在这一应用中，可以通过修改策略来找到最短路径。

---

八皇后问题

比如：arr[0] = 4，表示第1个皇后放在第1行的第5列。因为第n行就可以放第n个皇后。

事实上，回溯的效率很低，一个8皇后问题，就需要检测一万多次。

代码实现

package huisu;
 
/**
 * Created by wolf on 2016/3/16.
 */
public class WolfQueen {
    /**
     * 一共有多少个皇后（此时设置为8皇后在8X8棋盘，可以修改此值来设置N皇后问题）
     */
    int max = 8;
    /**
     * 该数组保存结果，第一个皇后摆在array[0]列，第二个摆在array[1]列
     */
    int[] array = new int[max];
 
    public static void main(String[] args) {
        new WolfQueen().check(0);
    }
 
    /**
     * n代表当前是第几个皇后
     * @param n
     * 皇后n在array[n]列
     */
    private void check(int n) {
        //终止条件是最后一行已经摆完，由于每摆一步都会校验是否有冲突，所以只要最后一行摆完，说明已经得到了一个正确解
        if (n == max) {
            print();
            return;
        }
        //从第一列开始放值，然后判断是否和本行本列本斜线有冲突，如果OK，就进入下一行的逻辑
        for (int i = 0; i < max; i++) {
            array[n] = i;
            if (judge(n)) {
                check(n + 1);
            }
        }
    }
 
    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;
    }
 
    private void print()  {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + 1 + " ");
        }
        System.out.println();
    }
}