递归：分为递和归两个动作。
简单通俗的来说，就是当前步骤发现自己处理不了，那么就“递”出去，让别人处理；
每个步骤都检查自己能不能处理，直到有一个环节能处理，处理完则“归”回来。
这是递归比较形象的说法。
规范一点的说法就是：
1、问题能够拆解成n个小的任务，每个任务的处理逻辑是一样的，这就是一个拆解任务并自己调用自己的过程；
2、任务最终不能再分解，这是一个有最终返回条件，防止无限递归。
总结：找递推公式和终止条件。
实战：
n个台阶，一次可以走一个台阶或者两个台阶，一共有多少种走法
递推公式：
f(n) = f(1) + f(2)
终止条件：
n==1 or n==2
int fun(int n) {
if(n==1) return 1;
if(n==2) return 2;
return f(n-1)+f(n-2);
} 分析：
if(n==1) return 1 表示最后剩下一个台阶，那么肯定只有一种走法；
if(n==2) return 2 表示最后剩下两个台阶，那么就有两种走法，一种是一次一个台阶，一种是一次两台台阶。
注意：
1、要注意栈溢出；
2、要考虑重复计算。
问题一栈溢出很好理解，当你不停的递归，当前函数会不断被压入栈中，当递归次数过多，超过栈的大小，就会产生这样的错误提示：
Exception in thread “main” java.lang.StackOverflowError
问题二的重复计算的问题，是因为递归过程中会有一些步骤计算重叠，以上面台阶为例
f7
f6 f5
f5 f4 f4 f3
f4 f3 f3 f2 ... ...
... ... ... ... ... ...我们可以看到从f5往下，都存在重复计算，f5的节点有两个，其实只计算一次就可以了，f4的节点有3个，也是只计算一次就可以了，其他都是如此。
重复计算就意味着浪费性能，需要做针对的优化。
所以上面的函数优化后如下：
Map<Integer, Integer> values = new HashMap<>();
int fun(int n) {
if(n==1) return 1;
if(n==2) return 2;
if(values.containsKey(n)) {
return values.get(n);
}
int result = f(n-1)+f(n-2)
values.put(n, result)
return result;
}