前一节课讲解了几种经典的排序算法。面试主要考察的是分析和处理问题的能力，而排序算法的一些思想是非常常用的，例如归并排序和快速排序采用的分治法就是高效的算法思想。这节课将介绍：递归和回溯。
递归和回溯的关系密不可分：
* 递归的基本性质就是函数调用，在处理问题的时候，递归往往是把一个大规模的问题不断地变小然后进行推导的过程。
* 回溯则是利用递归的性质，从问题的起始点出发，不断地进行尝试，回头一步甚至多步再做选择，直到最终抵达终点的过程。
* [ ] 递归（Recursion）
* 算法思想
递归算法是一种调用自身函数的算法（二叉树的许多性质在定义上就满足递归）。
举例：（汉诺塔问题）有三个塔 A、B、C，一开始的时候，在塔 A 上放着 n 个盘子，它们自底向上按照从大到小的顺序叠放。现在要求将塔 A 中所有的盘子搬到塔 C 上，让你打印出搬运的步骤。在搬运的过程中，每次只能搬运一个盘子，另外，任何时候，无论在哪个塔上，大盘子不能放在小盘子的上面。
解法：
从最终的结果出发，要把 n 个盘子按照大小顺序叠放在塔 C 上，就需要将塔 A 的底部最大的盘子搬到塔 C；
为了实现步骤 1，需要将除了这个最大盘子之外的其余盘子都放到塔 B 上。
由上可知，将原来的问题规模从 n 个盘子变成了 n-1 个盘子，即将 n-1 个盘子转移到塔 B 上。
如果一个函数，能将 n 个盘子从塔 A，借助塔 B，搬到塔 C。那么，也可以利用该函数将 n-1 个盘子从塔 A，借助塔 C，搬到塔 B。同理，不断地把问题规模变小，当 n 为 1，也就是只有 1 个盘子的时候，直接打印出步骤。
代码：
```
void hano(char A, char B, char C, int n) {
if (n > 0) {
hano(A, C, B, n - 1);
move(A, C);
hano(B, A, C, n - 1);
}
}
```
由上述总结出递归的算法思想，将一个问题的规模变小，然后再利用从小规模问题中得出的结果，结合当前的值或者情况，得出最终的结果。
通俗来说，把要实现的递归函数看成是已经实现好的， 直接利用解决一些子问题，然后需要考虑的就是如何根据子问题的解以及当前面对的情况得出答案。这种算法也被称为自顶向下（Top-Down）的算法。
* [ ] 例题分析一
LeetCode 第 91 题，解码的方法。
一条包含字母 A-Z 的消息通过以下方式进行了编码：
```
'A' -> 1
'B' -> 2
…
'Z' -> 26
```
给定一个只包含数字的非空字符串，请计算解码方法的总数。
**解题思路**
就例题中的第二个例子，给定编码后的消息是字符串“226”，如果对其中“22”的解码有 m 种可能，那么，加多一个“6”在最后，相当于在最终解密出来的字符串里多了一个“F”字符而已，总体的解码还是只有 m 种。
对于“6”而言，如果它的前面是”1”或者“2”，那么它就有可能是“16”，“26”，所以还可以再往前看一个字符，发现它是“26”。而前面的解码组合是 k 个，那么在这 k 个解出的编码里，添加一个“Z”，所以总的解码个数就是 m+k。
**代码实现**
```
int numDecodings(String s) {
if (s.charAt(0) == '0') return 0;
char[] chars = s.toCharArray();
return decode(chars, chars.length - 1);
}
// 字符串转换成字符数组，利用递归函数 decode，从最后一个字符向前递归
int decode(char[] chars, int index) {
// 处理到了第一个字符,只能有一种解码方法，返回 1
if (index <= 0) return 1;
int count = 0;
char curr = chars[index];
char prev = chars[index - 1];
// 当前字符比 “0” 大，则直接利用它之前的字符串所求得的结果
if (curr > '0') {
count = decode(chars, index - 1);
}
// 由前一个字符和当前字符所构成的数字，值必须要在 1 到 26 之间，否则无法进行解码
if (prev == '1' || (prev == '2' && curr <= '6')) {
count += decode(chars, index - 2);
}
return count;
}
```
**解题模板**
通过上述例题，来归纳总结一下递归函数的解题模版。
**解题步骤**
1. 判断当前情况是否非法，如果非法就立即返回，这一步也被称为完整性检查（Sanity Check）。例如，看看当前处理的情况是否越界，是否出现了不满足条件的情况。通常，这一部分代码都是写在最前面的。
2. 判断是否满足结束递归的条件。在这一步当中，处理的基本上都是一些推导过程当中所定义的初始情况。
3. 将问题的规模缩小，递归调用。在归并排序和快速排序中，我们将问题的规模缩小了一半，而在汉诺塔和解码的例子中，我们将问题的规模缩小了一个。
4. 利用在小规模问题中的答案，结合当前的数据进行整合，得出最终的答案。
**代码实现**
```
function fn(n) {
// 第一步：判断输入或者状态是否非法？
if (input/state is invalid) {
return;
}
// 第二步：判读递归是否应当结束?
if (match condition) {
return some value;
}
// 第三步：缩小问题规模
result1 = fn(n1)
result2 = fn(n2)
...
// 第四步: 整合结果
return combine(result1, result2)
}
```
* [ ] 例题分析二
LeetCode 第 247 题：找到所有长度为 n 的中心对称数。
**示例**
```
输入: n = 2
输出: ["11","69","88","96"]
```
**解题思路**
* 当 n=0 的时候，应该输出空字符串：“ ”。
* 当 n=1 的时候，也就是长度为 1 的中心对称数有：0，1，8。
* 当 n=2 的时候，长度为 2 的中心对称数有：11， 69，88，96。注意：00 并不是一个合法的结果。
* 当 n=3 的时候，只需要在长度为 1 的合法中心对称数的基础上，不断地在两边添加 11，69，88，96 就可以了。
```
[101, 609, 808, 906, 111, 619, 818, 916, 181, 689, 888, 986]
```
随着 n 不断地增长，我们只需要在长度为 n-2 的中心对称数两边添加 11，69，88，96 即可。
**代码实现**
```
List<String> helper(int n, int m) {
// 第一步：判断输入或者状态是否非法？
if (n < 0 || m < 0 || n > m) {
throw new IllegalArgumentException("invalid input");
}
// 第二步：判读递归是否应当结束?
if (n == 0) return new ArrayList<String>(Arrays.asList(""));
if (n == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));
// 第三步：缩小问题规模
List<String> list = helper(n - 2, m);
// 第四步: 整合结果
List<String> res = new ArrayList<String>();
for (int i = 0; i < list.size(); i++) {
String s = list.get(i);
if (n != m) res.add("0" + s + "0");
res.add("1" + s + "1");
res.add("6" + s + "9");
res.add("8" + s + "8");
res.add("9" + s + "6");
}
return res;
}
```
**算法分析**
分析非递归算法的时间复杂度非常直接，例如，前一节课里分析过冒泡排序以及插入排序的时间复杂度，分析方法就是数有多少层循环，由于每层循环里面执行的操作都是对比和交换，时间复杂度是 O(1)，所以，最终的时间复杂度就是将每层循环的长度相乘。
分析递归算法推荐两种方法：
* 迭代法
* 公式法
* [ ] 迭代法
举例：分析汉诺塔递归函数的时间复杂度。
```
void hano(char A, char B, char C, int n) {
if (n > 0) {
hano(A, C, B, n - 1);
move(A, C);
hano(B, A, C, n - 1);
}
}
```
假设这个递归函数的运行时间是 T(n)。
1. if 语句（一般取 if 块或 else 块之间最大的时间复杂度）中，比较和判断 n 的大小，CPU 的执行时间为 1 个单位。
2. 两次调用递归函数，每次都使问题的规模减少 1 个，得到两倍的 T(n-1)。打印输出的语句，CPU 的执行时间也为 1 个单位。因此得出：T(n) = 1 + 2×T(n - 1) + 1。
此处 if 语句和打印输出语句的执行时间与问题规模 n 无关，因此它们的算法时间复杂度可以记为 O(1)，表达式变为：T(n) = 2×T(n - 1) + O(1)。
当 n=0 的时候，T(0) = 1，因为当没有盘子的时候，if 语句也要进行一次比较，判断 n 是否大于 0。
3. 用迭代法将 T(n) 进行展开。
T(n - 1) = 2×T(n - 2) + 1，以此类推，不断地代入到 T(n) 的表达式当中，得到如下关系：
```
T(n) = 2× (2×T(n - 2) + 1) + 1 = 22×T(n - 2) + (2 + 1)
T(n) = 2×(2× (2×T(n - 3) + 1) + 1) + 1 = 23×T(n - 3) + (4 + 2 + 1)
T(n) = 2×(2×(2×(2×T(n - 4) + 1) + 1) + 1) + 1 = 24×T(n - 4) + (8 + 4 + 2 + 1)
…
T(n) = 2k×T(n - k) + (2k - 1)
```
其中，1 + 2 + 4 + 8 + … 是一个等比数列，由求和公式得到 2k - 1。当 k 等于 n 的时候，T(n) = 2n×T(0) + (2n - 1)，由于 T(0) 等于 1，所以最终 T(n) = 2×2n - 1。
对 T(n) 求 O 的值得到：O(n) = O(T(n)) = O(2×2n - 1) ，忽略掉常量和系数，O(n) = O(2n)。
所以，整个算法的时间复杂度就是 O(2n)。
而很难通过迭代法推导出比较复杂的时间复杂度的时候，可以借用公式法。
* [ ] 公式法
公式法可以说是计算递归函数复杂度最方便的工具，当递归函数的时间执行函数满足如下的关系式时，我们可以利用公式法：T(n) = a×T(n/b) + f(n)。
其中，f(n) 是每次递归完毕之后额外的计算执行时间。例如，在归并排序中，每次递归处理完两边的数组后，我们需要执行合并的操作，那么这个操作的执行时间就是 f(n)。
当参数 a、b 都确定的时候，光看递归的部分，它的时间复杂度就是：O(n^logba)。
由于时间复杂度求的是上界（upper bound)，通过对比递归部分的时间复杂度和 f(n) 的大小关系，得出最后的整体时间复杂度。牢记以下三种情况和相应公式：
1. 当递归部分的执行时间 nlog(b)a 大于 f(n) 的时候，最终的时间复杂度就是 O(n^logba)。
2. 当递归部分的执行时间 nlog(b)a 小于 f(n) 的时候，最终的时间复杂度就是 f(n)。
3. 当递归部分的执行时间 nlog(b)a 等于 f(n) 的时候，最终的时间复杂度就是 O(n^logba)logn。
* 举例 1：分析归并排序的时间复杂度。
```
T(n) = 2T(n/2) + n
a = 2，b = 2，f(n) = n
logba = 1，n1 = n
```
符合第三种情况，最终的时间复杂度就是 O(nlogn)。
* 举例 2：分析下面函数的时间复杂度。
```
int recursiveFn(int n) {
if (n == 0) {
return 0;
}
return recursiveFn(n / 4) + recursiveFn(n / 4);
}
```
得出时间执行函数：T(n) = 2×T(n/4) + 1，a = 2，b = 4，f(n) = 1。
代入公式得到：n^log42 = n0.5，当 n>1 的时候，n0.5>1，因此，时间复杂度就是 O(n0.5)。
* 举例 3：已知时间执行函数如下，分析时间复杂度。
```
T(n) = 3×T(n/2) + n2
a = 3，b = 2，f(n) = n2
```
最复杂的操作发生在递归完成之后，符合第二种情况。
代入公式得到：n^log23 = n1.48<n2，最后递归的时间复杂度是 O(n2)。
* [ ] 小结
对于时间复杂度的分析是算法面试中非常重要的一环，掌握好迭代法和公式法，对于分析大多数面试题都有非常重要的帮助，需要通过不断地练习，来熟练运用它们。
* [ ] 回溯（Backtracking）
* 算法思想
回溯实际上是一种试探算法，这种算法跟暴力搜索最大的不同在于，在回溯算法里，是一步一步地小心翼翼地进行向前试探，会对每一步探测到的情况进行评估，如果当前的情况已经无法满足要求，那么就没有必要继续进行下去，也就是说，它可以帮助我们避免走很多的弯路。
回溯算法的特点在于，当出现非法的情况时，算法可以回退到之前的情景，可以是返回一步，有时候甚至可以返回多步，然后再去尝试别的路径和办法。这也就意味着，想要采用回溯算法，就必须保证，每次都有多种尝试的可能。
* [ ] 解题模板
* 解题步骤
1. 判断当前情况是否非法，如果非法就立即返回；
2. 当前情况是否已经满足递归结束条件，如果是就将当前结果保存起来并返回；
3. 当前情况下，遍历所有可能出现的情况并进行下一步的尝试；
4. 递归完毕后，立即回溯，回溯的方法就是取消前一步进行的尝试。
代码模板
```
function fn(n) {
// 第一步：判断输入或者状态是否非法？
if (input/state is invalid) {
return;
}
// 第二步：判读递归是否应当结束?
if (match condition) {
return some value;
}
// 遍历所有可能出现的情况
for (all possible cases) {
// 第三步: 尝试下一步的可能性
solution.push(case)
// 递归
result = fn(m)
// 第四步：回溯到上一步
solution.pop(case)
}
}
```
* [ ] 例题分析一
LeetCode 第 39 题：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
说明：
* 所有数字（包括 target）都是正整数。
* 解集不能包含重复的组合。
**解题思路**
题目要求的是所有不重复的子集，而且子集里的元素的值的总和等于一个给定的目标。
* [ ] 思路 1：暴力法。
罗列出所有的子集组合，然后逐个判断它们的总和是否为给定的目标值。解法非常慢。
* [ ] 思路 2：回溯法。
1. 从一个空的集合开始，小心翼翼地往里面添加元素。
2. 每次添加，检查一下当前的总和是否等于给定的目标。
3. 如果总和已经超出了目标，说明没有必要再尝试其他的元素了，返回并尝试其他的元素；
4. 如果总和等于目标，就把当前的组合添加到结果当中，表明我们找到了一种满足要求的组合，同时返回，并试图寻找其他的集合。
代码实现
```
int[][] combinationSum(int[] candidates, int target) {
int[][] results;
backtracking(candidates, target, 0, [], results - 换另外一种颜色高亮);
return results;
}
void backtracking = (int[] candidates, int target, int start, int[] solution, int[][] results) => {
if (target < 0) {
return;
}
if (target === 0) {
results.push(solution);
return;
}
for (int i = start; i < candidates.length; i++) {
solution.push(candidates[i]);
backtracking(candidates, target - candidates[i], i, solution, results);
solution.pop();
}
}
```
在主函数里：
1. 定义一个 results 数组用来保存最终的结果；
2. 调用函数 backtracking，并将初始的情况以及 results 传递进去，这里的初始情况就是从第一个元素开始尝试，而且初始的子集为空。
在 backtracking 函数里：
1. 检查当前的元素总和是否已经超出了目标给定的值，每添加进一个新的元素时，就将它从目标总和中减去；
2. 如果总和已经超出了目标给定值，就立即返回，去尝试其他的数值；
3. 如果总和刚好等于目标值，就把当前的子集添加到结果中。
在循环体内：
1. 每次添加了一个新的元素，立即递归调用 backtracking，看是否找到了合适的子集
2. 递归完毕后，要把上次尝试的元素从子集里删除，这是最重要的。
以上，就完成了回溯。
提示：这是一个最经典的回溯的题目，麻雀虽小，但五脏俱全。它完整地体现了回溯算法的各个阶段。
* [ ] 例题分析二
LeetCode 第 51 题， 在一个 N×N 的国际象棋棋盘上放置 N 个皇后，每行一个并使她们不能互相攻击。给定一个整数 N，返回 N 皇后不同的的解决方案的数量。
* 解题思路
解决 N 皇后问题的关键就是如何判断当前各个皇后的摆放是否合法。
利用一个数组 columns[] 来记录每一行里皇后所在的列。例如，第一行的皇后如果放置在第 5 列的位置上，那么 columns[0] = 6。从第一行开始放置皇后，每行只放置一个，假设之前的摆放都不会产生冲突，现在将皇后放在第 row 行第 col 列上，检查一下这样的摆放是否合理。
方法就是沿着两个方向检查是否存在冲突就可以了。
* 代码实现
首先，从第一行开始直到第 row 行的前一行为止，看那一行所放置的皇后是否在 col 列上，或者是不是在它的对角线上，代码如下。
```
boolean check(int row, int col, int[] columns) {
for (int r = 0; r < row; r++) {
if (columns[r] == col || row - r == Math.abs(columns[r] - col)) {
return false;
}
}
return true;
}
```
然后进行回溯的操作，代码如下。
```
int count;
int totalNQueens(int n) {
count = 0;
backtracking(n, 0, new int[n]);
return count;
}
void backtracking(int n, int row, int[] columns) {
// 是否在所有n行里都摆放好了皇后？
if (row == n) {
count++; // 找到了新的摆放方法
return;
}
// 尝试着将皇后放置在当前行中的每一列
for (int col = 0; col < n; col++) {
columns[row] = col;
// 检查是否合法，如果合法就继续到下一行
if (check(row, col, columns)) {
backtracking(n, row + 1, columns);
}
// 如果不合法，就不要把皇后放在这列中（回溯）
columns[row] = -1;
}
}
```
**算法分析**
回溯其实是用递归实现的，因此我们在分析回溯的时间复杂度时，其实就是在对递归函数进行分析，方法和之前介绍的一样。
举例：分析一下 N 皇后的时间复杂度。
假设 backtracking 函数的执行时间是 T(n)。
解法：
1. 每次都必须遍历所有的列，一共有 n 列。
2. 在每次遍历中，先要利用 check 函数检查当前的摆放方法会不会产生冲突，检查的时间复杂度由当前所在的行决定，上限是 n，所以总时间复杂度就是 O(n2)。
3. 递归地尝试着每种摆放，当我们放好了第一个皇后，剩下要处理的之后 n-1 个皇后，问题的规模减少了一个，于是执行时间变成了 T(n - 1)。
最终得到了 T(n) 的表达式：T(n) = n×T(n - 1) + O(n2)。
利用迭代法将 T(n) 展开得到：
```
T(n) = n×((n - 1)×T(n - 2) + (n - 1)2 + n2
…
T(n) = n×(n - 1)×(n - 2)× … ×1 + 1 + 22 + 32 + … (n - 1)2 + n2
```
前面一部分是阶乘，后面一部分是平方求和，根据公式最后得到：
```
T(n) = n! + n(n+1)(2n+1)/6
O(T(n)) = n! + O(n3)
```
由于 n!>n3，因此，它的上界就是 n!，即：O(T(n)) = n!
* [ ] 结语
递归和回溯可以说是算法面试中最重要的算法考察点之一，很多其他算法都有它们的影子。例如，二叉树的定义和遍历就利用到了递归的性质；归并排序、快速排序的时候也运用了递归；我们将在第 6 课介绍动态规划，它其实是对递归的一种优化；还有第 7 课里的二分搜索，也可以利用递归去实现。
注意：要能熟练掌握好分析递归复杂度的方法，必须得有比较扎实的数学基础，比如对等差数列、等比数列等求和公式要牢记。
建议：LeetCode 上对递归和回溯的题目分类做得很好，有丰富的题库，建议大家多做。
