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

假设有 {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;    }}

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