递归常用来解决一些可拆分的，并且拆分到一定程度自然得到解的问题，最经典的就是斐波那契数列（1，1，2，3，5......），从第三个数开始，每个数的值都为前面两个数的和，如第五个数字等于第三个数字加上第四个数字的和，第N个等于第N-1个数字加上第N-2数字的和
public static int Fibonacci(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 1;
}
return Fibonacci(n-1)+Fibonacci(n-2);
代码看起来很简单，实际上效率很低，当我们计算的数据很大的时候，比如第五十位数，会进行非常多次的分解，如果将运行的顺序抽象为一张类似二叉树的图的话，就能清晰的看到这种直接递归的缺点
图片.png
计算数列第五位数字的时候，运行的步骤是这样的，可以看到重复了两次第三位的结果，随着位数的增加，重复的计算也会急剧上升，我们可以通过一个数组或者集合来保存我们计算过的数据，遇到重复的计算的时候直接从集合中获取
public static int Fibonacci(int n) {
int memo[]=new int[n+1];
return Fibonacci(n,memo);
}
public static int Fibonacci(int n,int [] memo) {
if (memo[n]>0){
return memo[n];
}
if (n==1){
return 1;
}
else if (n==2){
return 1;
}else {
memo[n]=Fibonacci(n-1,memo)+Fibonacci(n-2,memo);
}
return memo[n];
}
这样的话，我们的计算效率就会提高很多了
