浅显易懂的理解-递归求全排列 递归法求全排列

提起递归，大多数人都会头疼，其实写递归代码的关键就是找到递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 只要遇到递归，我们就把它抽象成一个递推公式，千万不要想一层层的调用关系，不要试图用人脑去分解递归的每个步骤，否则会越陷越深，越来越蒙，那咱们用求全排列还理解递归。

假设有 {1, 2, 3, ... n} 这样一个序列，现在要找出这个序列的全排列，第一位有 n 种可能性，确定了第一位后就是求解剩下 n - 1 个数据的排列问题，这样就可以往下一直分解问题，直到序列结尾处，也就是终止条件。这样递推公式就可以表示成：

f(1, 2, ... n) = {第一位是 1, f(n-1)} + {第一位是 2, f(n-1)} +...+{第一位是 n, f(n-1)}

数组 {1, 2, 3, 4}，第一位有 4 种可能性：

1, 2, 3, 4

2, 1, 3, 4

3, 2, 1, 4

4, 2, 3, 1

就是将第一位和后面的数依次交换 ：

public class PermutationAdvanced {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4};
        allPermutation(a, 0,a.length - 1);
    }
    private static void allPermutation(int[] a, int cursor, int k) {
        for (int i = cursor; i <= k; i++) {
            swap(a, cursor, i);
            System.out.println(Arrays.toString(a));
            // 保证交换之前的序列还是 {1, 2, 3, 4}，所以还得交换回来
            swap(a, cursor, i);
        }
    }
    private static void swap(int[] a, int cursor, int i) {
        int temp = a[cursor];
        a[cursor] = a[i];
        a[i] = temp;
    }
}

第一个元素的代码抽象出来了，然后加入递归，剩下的 n - 1 或 n - 2 或 n - 3… 排列情况和第一位是一样的。

public class PermutationAdvanced {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        allPermutation(a, 0, a.length - 1);
    }
    private static void allPermutation(int[] a, int cursor, int k) {
        // 递归终止条件
        // 已经到序列结尾了 
        if (cursor == k) {
            System.out.println(Arrays.toString(a));
        }
        for (int i = cursor; i <= k; i++) {
            swap(a, cursor, i);
            allPermutation(a, cursor + 1, k);
            // 保证交换之前的序列还是 {1, 2, 3, 4}
            swap(a, cursor, i);
        }
    }
    private static void swap(int[] a, int cursor, int i) {
        int temp = a[cursor];
        a[cursor] = a[i];
        a[i] = temp;
    }
}

这样是不是好理解了一点呢：）