递归，数据结构中最难理解的可能就是动态规划和递归了，但递归生活中很常用，出去的叫"递"，回来的叫"归"，所有递归都能写出数学表达式
1.递归的三个条件
分支:一个问题的解分成几个子问题的解，规模依次递减
分支关系:规模依次递减的问题，他们求解思路完全相同
终止条件:规模依次递减，就一定存在终止条件，即最小边界
注:由此可见，递归是从n规模倒推回去的，设n规模时解方法为f(n)，规模递减之后n-1/n-2但求解思路一样，所以他们解方法肯定一样f(n-2)或者f(n-1)
2.代码编写
难点:写出递归公式，找出终止条件
如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？如果有 7 个台阶，那如何用编程求得总共有多少种走法呢？
解:
a.递归式子
从规模n开始，设解方法为f(n)，由于到n规模前一次操作的规模是n-1或n-2，他们求解方法完全一样f(n-1)或f(n-2)，每次操作，都是如此，求总共和，故两者想加f(n)=f(n-1)+f(n-2)
b.终止条件
当最后一次递归操作(逆序)，等价最开始的一次操作(顺序)，走到台阶1(n=1)或台阶2(n=2)，对应走法为1，2(走到台阶2:2次1步/1次2步共两种)，解方法为f(1)=1，f(2)=2
c.警惕堆栈溢出
解决办法限制最大递归深度(也就是执行次数)，计数器解决，但这个不好用，不知道当前栈空间，计算也很难，所以10/50次可以考虑，超出最好不用
// 全局变量，表示递归的深度。
int depth = 0;
int f(int n) {
++depth；
if (depth > 1000) throw exception;
if (n == 1) return 1;
return f(n-1) + 1;
}
d.警惕重复计算
解决办法，另辟空间储存已求得的解，每次递归式子执行前，先判定是否已经存在，存在直接返回结果，不用再算
public int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
// hasSolvedList 可以理解成一个 Map，key 是 n，value 是 f(n)
if (hasSolvedList.containsKey(n)) {
return hasSovledList.get(n);
}
int ret = f(n-1) + f(n-2);
hasSovledList.put(n, ret);
return ret;
}
3.非递归实现
只是模拟递归实现过程，迭代循环过程，本质没有变，徒增了复杂度
4.递归代码的调试
单步追踪已经无法解决，打印日志发现递归值，结合条件断点调试
5.递归性能
递归代码虽然简洁高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所以，在编写递归代码的时候，一定要控制好这些副作用。
6.递归注意事项
递归只有一个分支时，很容易理解每一个步骤，但是递归有多个分支，如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A，再找分支关系(数学语言:求递归式子)
