一分鐘學(xué)一個算法題目。

今天我們要學(xué)習(xí)的是用遞歸算法求解斐波那契數(shù)列。

視頻教程鏈接：https://www.bilibili.com/video/BV1Wu4y1i7JJ/

首先我們要知道什么是斐波那契數(shù)列。

斐波那契數(shù)列，又稱黃金分割數(shù)列，是一個經(jīng)典的數(shù)學(xué)數(shù)列，其特點是第一項，第二項為1，后面每個數(shù)字都是前兩個數(shù)字之和。推導(dǎo)過程如視頻所示，非常非常簡單。

知道了斐波那契數(shù)列的定義后，我們將其代入到遞歸問題的分析當(dāng)中。

首先確定邊界條件，就是第一項和第二項為1，接著確定遞歸關(guān)系，后一項等于前兩項的和。確定了上面這些關(guān)系，我們就可以寫出下面的代碼了。

def fib(x):

    # 邊界條件
    if x==1 or x==2: return 1

    # 遞歸關(guān)系
    return fib(x-2)+fib(x-1)

print(fib(1))
print(fib(2))
print(fib(3))
print(fib(4))
print(fib(5))
print(fib(6))

沒錯，去掉注釋和空行后只有三行代碼，簡潔精煉是遞歸問題的共性，你學(xué)習(xí)過肯定深有體會。下面我們稍微解讀下代碼，這是一個求解斐波那契數(shù)列第n項數(shù)字的函數(shù)，函數(shù)名為fib，接受一個參數(shù)n。

如果n等于1或者2，那么就返回1，否則就返回fib(n-2)與fib(n-1)的和，怎么樣，腦子轉(zhuǎn)過來彎了嗎？沒錯，就是這么簡單。我們來嘗試運行使用函數(shù)檢驗一下正確性，發(fā)現(xiàn)都輸出了正確結(jié)果。

但是這個函數(shù)還有很大的優(yōu)化空間，在哪里呢？沒錯，遞歸算法讓我們使用簡潔的代碼解決復(fù)雜的問題。但他的時間復(fù)雜度很高，一不小心沒做好邊界與轉(zhuǎn)換關(guān)系判斷就會導(dǎo)致無限循環(huán)或者棧溢出。

我們以此題為例，假如我們要求解斐波那契數(shù)列的第一百項數(shù)字，那麼我們會得到這張調(diào)用關(guān)系圖，同一項會被重復(fù)計算非常非常多次。所以你運行此函數(shù)可能會導(dǎo)致很長時間都計算不出結(jié)果。

那么，我們該如何優(yōu)化呢？
我們該如何避免重復(fù)計算某一項的值呢？

我們可以在計算出每一項的時候，把計算結(jié)果存到一個字典里。這樣我們在每次計算前先去字典中尋找這一項，如果有值，那么直接拿出來使用，如果沒有，再計算它。

這樣的話我們就可以保證每一項僅被計算一次。運行時間也將會大大縮短。按照以上思路我們對代碼進(jìn)行如下變化。

def fib(n):

    # 邊界條件
    if n==1 or n==2: return 1

    if hash.get(n,0):
        return hash.get(n)

    # 遞歸關(guān)系
    ans=fib(n-2)+fib(n-1)
    hash[ans]=ans
    return ans

hash={}

在代碼中我們增加了以下變化：
每次計算某一項時先去集合中查詢，如果已經(jīng)計算過，那么直接返回值，如果沒有，則計算，并且在返回值之前先在集合中記錄一下。

這樣代碼的算法復(fù)雜度已經(jīng)優(yōu)化了很多了，沒有優(yōu)化版本求解第70項都非常費力，現(xiàn)在優(yōu)化后已經(jīng)可以輕松算出第100項了。但要想算出第一百項還是需要很久時間。

因為其中還存在大量的分支判斷。

而且此解法還遠(yuǎn)遠(yuǎn)不是最優(yōu)解法，關(guān)注up主，我們下集就來講講更快的方法。

更多寶藏

??????????????????????
項目倉庫看這里??：
https://github.com/w-x-x-w
https://gitee.com/w-_-x
公眾號名稱??：編程啟航
博客文章看這里??：
https://blog.csdn.net/weixin_62650212
視頻推送看這里??：
https://space.bilibili.com/1909782963文章來源地址http://www.zghlxwxcb.cn/news/detail-666149.html

到了這里，關(guān)于一分鐘學(xué)算法-遞歸-斐波那契數(shù)列遞歸解法及優(yōu)化的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！