递归算法之-斐波那契数列

递归实现：效率低，容易栈溢出，计算次数成指数型爆炸（二叉树）,时间复杂度为O(n^2)

public int fun(int n){
    if(n==0) n=1;
    else if(n==1) n=1;
    else 
        return fun(n-1)+fun(n-2);
}

尾递归实现:效率高，时间复杂度为O(n)
a,b分别为n=0,n=1的值

public int fun(int a,int b,int n){
   if(n==0) return b;//递归到最后将和，也就是b返回
   return fun(b,a+b,n-1); 
}

动态规划(和尾递归本质是一样的)
思想，按照自顶向上的思想的话，要知道f(9)得先求f(8)和f(7)，这样下来就是计算就形成了二叉树的形式，有很多重复的计算，如果反过来想，自底向上去计算，即知道了f(1)和f(2)自然就得到了f(3),知道了f(2)和f(3),自然就知道了f(4)，也就是说我们只需保存前两个计算结果即可，这样就可以在O(n)内得到结果。

public int getTotal(int n){
    if(n==0) return 1;
    if(n==1) return 1;
    int a=1;
    int b=1;
    for(int i=2;i<=n;i++){//注意这里i从2算起
        int temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}