首先，递归问题一定先演算出其递推公式，找到终止条件。
我一开始在学习递归的时候，在纸上画出递归的过程，在脑子中像计算机一样回放一个个递归步骤，我发现这样反而进入了思维误区，给自己制造了理解障碍。递归就是将大问题分解为子问题，将最终的子问题的解作为终止条件，而这些子问题和大问题的解法都是一样的，只需要思考大问题和子问题之间的关系就行，不需要一层层往下去思考子问题与子子问题之间的关系。这样大脑一下就轻松了，原来这才是本质。
摘自极客时间王争老师的《数据结构与算法之美》专栏：

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

下面来一步步解析全排列算法的递归解法。

确定递推公式

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

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

第一位的排列情况

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

  1. 1, 2, 3, 4
  2. 2, 1, 3, 4
  3. 3, 2, 1, 4
  4. 4, 2, 3, 1

就是将第一位和后面的数依次交换，交换之前的序列是 {1, 2, 3, 4}：

  1. public class PermutationAdvanced {
  2.     public static void main(String[] args) {
  3.         int[] a = {1, 2, 3, 4};
  4.         allPermutation(a, 0,a.length - 1);
  6.     }
  8.     private static void allPermutation(int[] a, int cursor, int k) {
  9.         for (int i = cursor; i <= k; i++) {
  10.             swap(a, cursor, i);
  11.             System.out.println(Arrays.toString(a));
  12.             // 保证交换之前的序列还是 {1, 2, 3, 4}
  13.             swap(a, cursor, i);
  14.         }
  15.     }
  17.     private static void swap(int[] a, int cursor, int i) {
  18.         int temp = a[cursor];
  19.         a[cursor] = a[i];
  20.         a[i] = temp;
  21.     }
  22. }

输出：

  1. [1, 2, 3, 4]
  2. [2, 1, 3, 4]
  3. [3, 2, 1, 4]
  4. [4, 2, 3, 1]

重复元素的序列

序列 {3, 3, 2, 3, 4} 在上面的代码中输出是：

  1. [3, 3, 2, 3, 4]
  2. [3, 3, 2, 3, 4]
  3. [2, 3, 3, 3, 4]
  4. [3, 3, 2, 3, 4]
  5. [4, 3, 2, 3, 3]

这个序列第一位只有 3 种情况：3，2，4。所以还得针对存在重复元素的序列改进代码：

  2. public class PermutationAdvanced {
  3.     public static void main(String[] args) {
  4. //        int[] a = {1, 2, 3, 4};
  5.         int[] a = {3, 3, 2, 3, 4};
  6.         allPermutation(a, 0, a.length - 1);
  8.     }
  10.     private static void allPermutation(int[] a, int cursor, int k) {
  11.         for (int i = cursor; i <= k; i++) {
  12.             if (!judgeSwap(a, cursor, i)) {
  13.                 continue;
  14.             }
  15.             swap(a, cursor, i);
  16.             System.out.println(Arrays.toString(a));
  17.             // 保证交换之前的序列还是 {1, 2, 3, 4}
  18.             swap(a, cursor, i);
  19.         }
  20.     }
  22.     private static void swap(int[] a, int cursor, int i) {
  23.         int temp = a[cursor];
  24.         a[cursor] = a[i];
  25.         a[i] = temp;
  26.     }
  28.     /**
  29.      * 判断是否需要进行交换
  30.      *
  31.      * @param a
  32.      * @param cursor
  33.      * @param i
  34.      * @return
  35.      */
  36.     private static boolean judgeSwap(int[] a, int cursor, int i) {
  37.         for (int j = cursor; j < i; j++) {
  38.             /**
  39.              * a[i] 是等待被交换的元素
  40.              * 如果 cursor == i 需要进行交换
  41.              * 如果 在 [cursor, i) 范围里存在和 a[i] 相同的元素则不进行交换，说明这种情况已经存在了
  42.              */
  43.             if (a[j] == a[i]) {
  44.                 return false;
  45.             }
  46.         }
  47.         return true;
  48.     }
  49. }

输出：

  1. [3, 3, 2, 3, 4]
  2. [2, 3, 3, 3, 4]
  3. [4, 3, 2, 3, 3]

加入递归

通过代码将序列第一位的所有情况的罗列出来了，序列剩下的 n - 1 或 n - 2 或 n - 3… 排列情况和第一位是一样的：

  1. public class PermutationAdvanced {
  2.     public static void main(String[] args) {
  3.         int[] a = {1, 2, 3};
  4. //        int[] a = {3, 3, 2, 3, 4};
  5.         allPermutation(a, 0, a.length - 1);
  7.     }
  9.     private static void allPermutation(int[] a, int cursor, int k) {
  10.         // 递归终止条件
  11.         // 已经到序列结尾了 
  12.         if (cursor == k) {
  13.             System.out.println(Arrays.toString(a));
  14.         }
  15.         for (int i = cursor; i <= k; i++) {
  16.             if (!judgeSwap(a, cursor, i)) {
  17.                 continue;
  18.             }
  19.             swap(a, cursor, i);
  20.             allPermutation(a, cursor + 1, k);
  21.             // 保证交换之前的序列还是 {1, 2, 3, 4}
  22.             swap(a, cursor, i);
  23.         }
  24.     }
  26.     private static void swap(int[] a, int cursor, int i) {
  27.         int temp = a[cursor];
  28.         a[cursor] = a[i];
  29.         a[i] = temp;
  30.     }
  32.     /**
  33.      * 判断是否需要进行交换
  34.      *
  35.      * @param a
  36.      * @param cursor
  37.      * @param i
  38.      * @return
  39.      */
  40.     private static boolean judgeSwap(int[] a, int cursor, int i) {
  41.         for (int j = cursor; j < i; j++) {
  42.             /**
  43.              * a[i] 是等待被交换的元素
  44.              * 如果 cursor == i 需要进行交换
  45.              * 如果 在 [cursor, i) 范围里存在和 a[i] 相同的元素则不进行交换，说明这种情况已经存在了
  46.              */
  47.             if (a[j] == a[i]) {
  48.                 return false;
  49.             }
  50.         }
  51.         return true;
  52.     }

时间复杂度

第一层分解有 n 次交换操作；
第二层有 n 个节点，每个节点 n - 1 次交换，第二层交换次数为 n * (n - 1);
第三层的节点数就是上一层的交换次数 n * (n - 1)，每个结点交换 n - 2 次，第三层的交换次数为 n * (n - 1) * (n - 2)；
…
那第 k 层交换次数可以 表示成：n * (n - 1) * (n - 2) * ... * (n - k + 1)。
那总的交换次数就是各层加起来：

  1. n + n * (n - 1) + n * (n - 1) * (n - 2) + ... + n * (n - 1) * (n - 2) * ... * 2 * 1

最后一个数 n * (n - 1) * (n - 2) * ... * 2 * 1 等于 n!，前面的每个数肯定都是小于 n!，那这个公式的和小于 n * n!，可以看出全排列递归的时间复杂度是大于 O (n!)，小于O(n * n!)的，时间复杂度还是挺高的哦。

总结

如果要通过人脑去过一遍递归的过程，那是很困难的，当然也没这个必要。求解的递归的关键点是：

  1. 一个问题是否可以分解为多个子问题，然后子问题又可以继续划分；
  2. 分解后的子问题除了数据规模不一样，但具体解法还是一样。在全排列的求解过程中，每个子问题的解法一样，那就先解出一个子问题（求第一位有多少种情况），然后再加入递归代码，大脑中不用去模拟递归的一个过程，你就想子问题的解法都是一样的，计算机只不过是在通过栈做重复的事情而已；
  3. 找到子问题终止条件。