題目10：斐波那契數(shù)列

斐波那契數(shù)脏款，亦稱之為斐波那契數(shù)列（意大利語： Successione di Fibonacci)围苫，又稱黃金分割數(shù)列、費(fèi)波那西數(shù)列撤师、費(fèi)波拿契數(shù)剂府、費(fèi)氏數(shù)列剃盾，指的是這樣一個(gè)數(shù)列：1腺占、1、2痒谴、3衰伯、5、8积蔚、13意鲸、21、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞歸的方法定義：F0=0怎顾，F(xiàn)1=1论矾，F(xiàn)n=F(n-1)+F(n-2)（n>=2，n∈N*）杆勇，用文字來說贪壳，就是斐波那契數(shù)列由 0 和 1 開始，之后的斐波那契數(shù)列系數(shù)就由之前的兩數(shù)相加

思路

一. 基于遞歸

當(dāng)追求代碼的簡潔性蚜退，且遞歸的次數(shù)沒有足夠大時(shí)闰靴，使用遞歸

斐波那契數(shù)列

二. 基于循環(huán)

當(dāng)追求代碼的時(shí)間效率，那么使用循環(huán)會(huì)更好钻注÷烨遥基于遞歸的斐波那契數(shù)列在每次計(jì)算的時(shí)候都存在重復(fù)的計(jì)算，其時(shí)間復(fù)雜度會(huì)隨著n的增加以指數(shù)的方式遞增幅恋。并且杏死，使用遞歸可能會(huì)引起調(diào)用棧溢出的問題。

重復(fù)計(jì)算

用有限變量避免遞歸的重復(fù)計(jì)算

代碼實(shí)現(xiàn)

public class _10 {
    public static long fibonacci1(int n) {
        if(n <= 0)
            return 0;
        if(n == 1)
            return 1;
        return fibonacci1(n - 1) + fibonacci1(n - 2);
    }
    
    public static long fibonacci2(int n) {
        if (n <= 0) {
            return 0;
        }     
        if (n == 1 ) {// 輸入1的時(shí)候返回1
            return 1;
        }
        long prePre = 0;//初始化為第一個(gè)fibonacci的值捆交，記錄第n-2個(gè)的Fibonacci數(shù)的值      
        long pre = 1;//初始化為第二個(gè)fibonacci的值淑翼， 記錄第n-1個(gè)的Fibonacci數(shù)的值
        long current = 0; // 記錄第n個(gè)的Fibonacci數(shù)的值      
        for (int i = 2; i <= n ; i++) {    
            current = prePre + pre;
            // 更新記錄的結(jié)果，prePre原先記錄第i-2個(gè)Fibonacci數(shù)的值
            // 現(xiàn)在記錄第i-1個(gè)Fibonacci數(shù)的值
            prePre = pre;
            // 更新記錄的結(jié)果品追，pre原先記錄第i-1個(gè)Fibonacci數(shù)的值
            // 現(xiàn)在記錄第i個(gè)Fibonacci數(shù)的值
            pre = current;
        }
        return current;
    }
    
    public static void main(String[] args) {
        System.out.println("基于遞歸： ");
        System.out.println("fibonacci(0)="+fibonacci1(0));
        System.out.println("fibonacci(1)="+fibonacci1(1));
        System.out.println("fibonacci(2)="+fibonacci1(2));
        System.out.println("fibonacci(3)="+fibonacci1(3));
        System.out.println("fibonacci(4)="+fibonacci1(4));
        System.out.println("fibonacci(5)="+fibonacci1(5));
        System.out.println("fibonacci(6)="+fibonacci1(6));
        System.out.println("fibonacci(7)="+fibonacci1(7));
        System.out.println("基于循環(huán)： ");
        System.out.println("fibonacci(0)="+fibonacci2(0));
        System.out.println("fibonacci(1)="+fibonacci2(1));
        System.out.println("fibonacci(2)="+fibonacci2(2));
        System.out.println("fibonacci(3)="+fibonacci2(3));
        System.out.println("fibonacci(4)="+fibonacci2(4));
        System.out.println("fibonacci(5)="+fibonacci2(5));
        System.out.println("fibonacci(6)="+fibonacci2(6));
        System.out.println("fibonacci(7)="+fibonacci2(7));
    }
}

輸出：

基于遞歸： 
fibonacci(0)=0
fibonacci(1)=1
fibonacci(2)=1
fibonacci(3)=2
fibonacci(4)=3
fibonacci(5)=5
fibonacci(6)=8
fibonacci(7)=13
基于循環(huán)： 
fibonacci(0)=0
fibonacci(1)=1
fibonacci(2)=1
fibonacci(3)=2
fibonacci(4)=3
fibonacci(5)=5
fibonacci(6)=8
fibonacci(7)=13