递归
递归是非常广泛的计算机编程技巧，理解递归，只需要把这两个字拆解开就可以了，即 “递” 与 “归”，递就是把问题传递出去，或者叫把一个问题拆成下一个子问题求解。归就是把递出去的问题答案反向通知回来。
举一个上学时候的例子，军训的时候若干个同学排成一排，其中中间的某个同学不知道自己在第几排，这时候，这个同学就会问前边一个同学是第几排，前一个同学也不知道，只好继续往前问，直到问到第一排的同学说自己是在第一排，于是第二排的同学知道了自己在第二排，这样以此类推，把排数向后传回去，最初那个问自己在第几排的同学也就知道了答案。
所以递归具有以下两个特点：
1：当前求解的问题，可以拆解为规模更小的相同问题，小规模的问题和原问题求解思路完全相同。
2：存在边界条件，到达这个边界条件后，问题由“递”变为“归”。
计算机编程中，递归通常表现为函数自己调用自己(每次调用，问题规模更小)，直到达到边界后不再产生新的函数自调用，开始归的过程，最具代表性的递归求解的问题有以下几个：
- 数的阶乘：
int factorial (int n) {
if (n == 1) {
return 1;
}
return n * factorial(n - 1);
}
// 斐波那契序列 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...
int fibonacci (int n) {
if (n == 1) {
return 0;
}
if (n == 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
理论上递归都可以用循环来实现
递归其实就是循环的过程，只不过不是代码上的循环，而是函数调用栈的循环，所以理论上，递归问题都可以用循环迭代解决。
- 数的阶乘循环实现：
int factorial1 (int n) {
int ret = 1;
for (int i = 1; i <= n; i++) {
ret = i * ret;
}
return ret;
}
- 斐波那契序列循环实现
int fibonacci1 (int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 0;
}
if (n == 2) {
return 1;
}
int pre = 1;
int prepre = 0;
int ret = 0;
for (int i = 3; i<= n; i++) {
ret = prepre + pre;
prepre = pre;
pre = ret;
}
return ret;
}
很明显的可以看出，用递归的方式实现，代码更加简洁美观，但我们知道函数调用，会不停的开辟栈空间，递归实现尤其需要注意栈溢出问题，所以递归不适合大规模的问题编程求解。部分语言的编译器或者解释器支持了尾调用优化，再某种程度就是解决栈溢出问题，节省内存。
不要去脑展开递归的全过程
理解递归的时候，人脑本能的想把递归的全过程展开，但是人脑的脑容量通常是有限的，当问题规模很大的时候，人脑是无法展开全部的递归过程的，强行闹展开失败后，只会让自己怀疑自己的智力问题，进入思维误区；如果非要脑展开全过程，可以用很小的规模数展开验证。
例如下列递归问题：
假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个…请问走这 n 个台阶有多少种走法？对于这个问题，当台阶只有 3 个的时候，我们很容易想到有，2、1 或者 1、2 或者 1、1、1 三种走法，但是如果是 7 个台阶的时候，人脑就不能立刻想清楚到底有几种走法，这时，我们可能需要笔和纸来记录一部分走法，释放一部分脑容量，才能思考清楚。
而如果我们不展开全过程，用递归的方式思考，应该是这个样子的：
- 对于当前 n 个台阶的走法，仅考虑下一步的话，只有两种方式，即走 1 阶台阶或者走 2 阶台阶，这两种走法就会对当前 n 个台阶产生两种完全不同的路线；如果走 1 个台阶，问题就变为 n -1 个台阶走法的问题，如果走 2 个台阶，问题就变为 n – 2 个台阶走法的问题，所以得出通用的归纳法： f(n) = f(n-1) + f(n-2)；
- 存在边界，当最后只剩 1 个台阶时，只剩一种走法；如果剩余 2 个台阶，剩两种走法。
所以可以写出递归函数：
int ff (int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return ff(n - 1) + ff(n - 2);
}
递归中的重复计算
仔细看上边的 n 个台阶的走法的递归函数，其中会有重复的函数计算：
包括之前的斐波那契数列，多次调用后都会有重复的计算，我们可以稍加修改代码，来避免重复计算
int ff (int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
// solvedList 可以理解成一个 Map
if (solvedList.contain(n)) {
return solvedLis.get(n);
}
int ret = ff(n - 1) + ff(n - 2);
solvedLis.put(n, ret);
return ret;
}
(完)