斐波那契數(shù)列指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34......，仔細(xì)觀察這個(gè)數(shù)列的規(guī)律可得出，第0項(xiàng)和第一項(xiàng)分別是他們本身，從第二項(xiàng)開(kāi)始每一項(xiàng)等于前兩項(xiàng)相加之和，下面我們根據(jù)這個(gè)規(guī)律來(lái)實(shí)現(xiàn)以下求斐波那契數(shù)列的第N項(xiàng)

斐波那契數(shù)列的實(shí)現(xiàn)方法有很多種，下面我們用兩種方式實(shí)現(xiàn)一下(以下代碼都是C語(yǔ)言實(shí)現(xiàn))

一.遞歸算法實(shí)現(xiàn)

int Fibo1(int n)
{
    if (n < 2) {
        return n;
    }
    return Fibo1(n - 1) + Fibo1(n - 2);
}

二.for循環(huán)實(shí)現(xiàn)

int Fibo2(int n)
{
    if (n < 2) {
        return  n;
    }
    
    int sum;
    int first = 0;
    int second = 1;
    for (int i = 0; i < n - 1; i++) {
        sum = first + second;
        first = second;
        second = sum;
    }
    return second;
}

以上兩種實(shí)現(xiàn)方式對(duì)比，第一種的時(shí)間復(fù)雜度為O(2^n)，第二種的時(shí)間復(fù)雜度為O(n)，項(xiàng)目中為了節(jié)省運(yùn)行時(shí)間和空間，我們盡量采用復(fù)雜度低的算法來(lái)實(shí)現(xiàn)功能，所以比較推薦第二種實(shí)現(xiàn)方式。