[Java]費氏數列

費氏數列(fibonacci sequence)是程式語言中常見的遞迴範例
他的每一項分別是：
A0=0
A1=1
AN=A(N-1)+A(N-2)
也就是A2以後，每一項的值就是前兩項的值相加
使用遞迴的方法可以把費式數列的值做出來
以下是遞迴的範例

public class FibonacciTest {

  

 public static void main(String[] args) {
    
   System.out.println(fibonacci(50));    

 }

  

 public static long fibonacci(int x){

  if(x==1||x==2){

   return 1;

  }else {

   return fibonacci(x-1)+fibonacci(x-2);

  }  

 }  

}

但是使用遞迴的效能很差
所以如果有人提出這個問題
又沒有特別規定要用遞迴做出來的話
建議使用一般的迴圈來解決這個問題
效能會有明顯的改善
以下是範例

public class FibonacciDemo {



 public static void main(String[] args) {

  

  FibonacciDemo demo = new FibonacciDemo();

  System.out.println(demo.fibonacci(50));  

 }

 

 public long fibonacci(int n){

  if(n==0){

   return 0;

  } else {

   long x_1 = 0;

   long x_2 = 1;

   for(int i=0;i<n;i++){

    if(i>0){

     x_2 = x_2 + x_1;

     x_1 = x_2 - x_1;

    }
   
   }

   return x_2;

  }

 }


}