Paste_Image.png
思路：
方法一：
递归：每次调用都需要在内存栈中分配空间，需要时间和空间消耗；出现重复计算的问题；调用栈溢出
long Fabonacci(int n){
if(n=0)
return 0;
if(n=1)
return 1;
if(n>=2)
return Fabonacci(n-1)+Fabonacci(n-2)
}
出现重复计算
Paste_Image.png
方法二：
循环
int Fabonacci(int n){
int result [2]={0,1};
if(n<2)
return result[n];
int fibN=0;
int fibNMinusOne=1;
int fibNMinusTwo=0;
for(int i=2;i<=n;i++){
fibN= fibNMinusOne+ fibNMinusTwo;
fibNMinusTwo= fibNMinusOne;
fibNMinusOne=fibN;
}
return fibN;
}
