序列前9项为：0, 1, 1, 2, 3, 5, 8, 13, 21

 要注意非递归的话就是那一个变量帮助存储当前下一项的值，然后依次挪动两个指针往下即可

 注意如果n太大 会溢出

 

 1     

public 

static 

long fib(

int n){

 2         

if(n <= 1)

 3             

return n;

 4         

else

 5             

return fib(n-1) + fib(n-2);

 6     }

 7     

 8     

public 

static 

long fib2(

int n){

 9         

if(n==0)

10             

return 0;

11         

if(n<=2)

12             

return 1;

13         

int n1 = 1, n2 = 1;

14         

int sn = 0;

15         

for(

int i = 2; i< n; i++){

16             sn = n1 + n2;

17             n1 = n2;

18             n2 = sn;

19         }

20         

return sn;

21     }