【基礎(chǔ)算法】遞歸函數(shù)-斐波那契數(shù)列實(shí)現(xiàn)的優(yōu)化-創(chuàng)新互聯(lián)

遞歸學(xué)習(xí)

函數(shù)會(huì)遞歸調(diào)用自身
需要有退出條件，避免無限自調(diào)，導(dǎo)致堆棧溢出，程序奔潰

專注于為中小企業(yè)提供網(wǎng)站設(shè)計(jì)制作、網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)閩清免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了近1000家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。斐波那契數(shù)列

設(shè)數(shù)列{an}, 若滿足a0=0, a1=1,an=an-1+an-2(n>=2)
則稱數(shù)列{an}為斐波那契數(shù)列。

遞推公式: a0=0, a1=1,an=an-1+an-2(n>=2)

實(shí)現(xiàn)方法1：普通遞歸實(shí)現(xiàn)

int fib(int n)
    {
        return n< 2 ? n : fib(n-1) + fib(n-2);
    }

當(dāng)n比較大時(shí)，會(huì)導(dǎo)致兩個(gè)問題：
1、遞歸的深度大，耗時(shí)長；
2、最終的結(jié)果有可能超出int的大范圍

使用局部靜態(tài)來優(yōu)化：

對(duì)于已計(jì)算出來的結(jié)果直接返回即可，
不在已計(jì)算范圍內(nèi)的，據(jù)遞推公式從原有基礎(chǔ)上遞推到n，并保留中間有效計(jì)算結(jié)果

如果int 類型不滿足大范圍，可以將int 改為long long int

int fb(int n)
{
    static vectorfb{0, 1};

    if (n< fb.size()) {
        return fb[n];
    }

    int size = fb.size();
    for (int i = size; i<= n; i++) {
        fb.push_back(fb[i - 1] + fb[i - 2]);
    }
    return fb[n];
}

延伸學(xué)習(xí)
int的上限問題
C/C++如何得到int型大值
https://blog.csdn.net/wenzishou/article/details/44563387

MIN_INT = (((unsigned int)(-1))>>1)
在32位系統(tǒng)中 2^(32-1) = 2147483647

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁題目：【基礎(chǔ)算法】遞歸函數(shù)-斐波那契數(shù)列實(shí)現(xiàn)的優(yōu)化-創(chuàng)新互聯(lián)
標(biāo)題URL：http://bm7419.com/article24/diphje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、做網(wǎng)站、營銷型網(wǎng)站建設(shè)、App開發(fā)、企業(yè)建站、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)