關(guān)于遞歸的思考

lyning 發(fā)布于2019-07-25 10:38 / 2509人閱讀

摘要：之前有接觸過(guò)遞歸，看到別人寫(xiě)的遞歸函數(shù)的代碼，好生羨慕，怎么就能寫(xiě)這么好呢我怎么就想不到這樣寫(xiě)呢如此等等。

之前有接觸過(guò)遞歸，看到別人寫(xiě)的遞歸函數(shù)的代碼，好生羨慕，怎么就能寫(xiě)這么好呢？我怎么就想不到這樣寫(xiě)呢？如此等等。

就拿fibonacci函數(shù)來(lái)說(shuō)吧，一個(gè)普通的函數(shù)可能這樣寫(xiě)：

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

我看到這個(gè)函數(shù)的思考方式是這樣的：

1. 當(dāng)n=0時(shí)：返回0
2. 當(dāng)n=1時(shí)：返回1
3. 當(dāng)n=2時(shí)：
    1. 首先去調(diào)用n=1，返回1
    2. 再去調(diào)用n=0，返回0
    3. 把0和1相加返回1
4. 當(dāng)n=3時(shí)：
    1. 調(diào)用n=2
        1. 調(diào)用n=1，返回1
        2. 調(diào)用n=0，返回0
        3. 相加返回1
    2. 調(diào)用n=1，返回1
    3. 把1和1相加返回2
5. 等等

想到這我頭都要爆了，徹底被人家的函數(shù)折服了，看來(lái)我是寫(xiě)不成這么好的函數(shù)了。

但我轉(zhuǎn)念一想，這個(gè)函數(shù)的本質(zhì)是fibnacci序列，我何不回歸fibonacci本身呢？fibonacci用數(shù)學(xué)公式表示應(yīng)該是這樣：

看到公式我恍然大悟，上面那個(gè)函數(shù)不就是根據(jù)這個(gè)公式直接翻譯的嘛！原來(lái)我一直思考都是順著函數(shù)的代碼思考，這樣肯定會(huì)覺(jué)得很難,
正確的思考方式應(yīng)該是從算法出發(fā)然后再寫(xiě)代碼。

經(jīng)過(guò)了上面的慘痛教訓(xùn)看看我能不能寫(xiě)出正確的fibonacci序列函數(shù)，分段函數(shù)的公式應(yīng)該是這樣的：

那么直接寫(xiě)成代碼就應(yīng)該是這樣的:

def fib_seq(n):
    seq = []
    if n == 0:
        seq.append(0)
    else:
        seq.extend(fib_seq(n-1))
        seq.append(fib(n))
    return seq

咦，這兩個(gè)append好像可以合并：

def fib_seq(n):
    seq = []
    if n > 0:
        seq.extend(fib_seq(n-1))
    seq.append(fib(n))
    return seq

哇，原來(lái)如此！

GPU云服務(wù)器云服務(wù)器人工智能的思考對(duì)人工智能的思考 python中的遞歸 java的遞歸樹(shù)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/38075.html

相關(guān)文章

Python | 遞歸

摘要：那假如我們用遞歸來(lái)描述這種情況呢定義基本情況其它情形所以在上述求和中的定義又用到了自己本身的定義，這就構(gòu)成了遞歸。說(shuō)起遞歸，我覺(jué)得其實(shí)大部分人應(yīng)該是不陌生的，遞歸廣泛存在于生活中。比如： showImg(https://segmentfault.com/img/remote/1460000007420204?w=294&h=450); The woman in this image ...

qieangel2013 2019-07-31 10:52 評(píng)論0 收藏0
《java 8 實(shí)戰(zhàn)》讀書(shū)筆記 -第十三章函數(shù)式的思考

摘要：當(dāng)我們希望能界定這二者之間的區(qū)別時(shí)，我們將第一種稱(chēng)為純粹的函數(shù)式編程，后者稱(chēng)為函數(shù)式編程。函數(shù)式編程我們的準(zhǔn)則是，被稱(chēng)為函數(shù)式的函數(shù)或方法都只能修改本地變量。另一種觀點(diǎn)支持引用透明的函數(shù)式編程，認(rèn)為方法不應(yīng)該有對(duì)外部可見(jiàn)的對(duì)象修改。一、實(shí)現(xiàn)和維護(hù)系統(tǒng) 1.共享的可變數(shù)據(jù) 如果一個(gè)方法既不修改它內(nèi)嵌類(lèi)的狀態(tài)，也不修改其他對(duì)象的狀態(tài)，使用return返回所有的計(jì)算結(jié)果，那么我們稱(chēng)其為純粹...

Donne 2019-08-16 17:14 評(píng)論0 收藏0
leetcode100 Same Tree 引發(fā)的對(duì)遍歷?算法的思考

摘要：判斷兩棵樹(shù)是否是相同題目要求傳入兩棵樹(shù)的根節(jié)點(diǎn)，判斷這兩棵樹(shù)是否相同此題的核心就在于如何遍歷樹(shù)。定義樹(shù)的一種自然方式是遞歸的方式。一棵樹(shù)是一些節(jié)點(diǎn)的集合，這個(gè)集合可以是空集。這個(gè)遍歷算法可以用于場(chǎng)景如，計(jì)算一個(gè)節(jié)點(diǎn)的高度。判斷兩棵樹(shù)是否是相同題目要求：傳入兩棵樹(shù)的根節(jié)點(diǎn)，判斷這兩棵樹(shù)是否相同此題的核心就在于如何遍歷樹(shù)。一旦我們解決了這個(gè)問(wèn)題，題目也就迎刃而解了。下面就來(lái)介紹一下關(guān)...

cyrils 2019-08-14 17:52 評(píng)論0 收藏0
記一次XX前端面試

摘要：面試官說(shuō)那我問(wèn)你一個(gè)哲學(xué)的問(wèn)題，為什么有數(shù)據(jù)結(jié)構(gòu)這種東西哇，這是啥，巴拉巴拉扯了一通，大致就是物以類(lèi)聚，人以群分，先人積累下來(lái)的經(jīng)驗(yàn)，這些讓我們更方便處理數(shù)據(jù)啥的。前因，沒(méi)有比摸魚(yú)有趣的事了距離自己被外派(俗稱(chēng)外包)出去，已經(jīng)過(guò)了快五個(gè)月，工作的話(huà)，很閑。人啊，一定保持好的習(xí)慣，懶惰是會(huì)上癮，日常摸魚(yú)，懷疑人生，我是誰(shuí)，我在哪，我要干什么。中午吃飯的時(shí)候，收到了boss直聘的一條...

Shisui 2019-08-22 17:21 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法之精講「遞歸系列」

摘要：終止條件遞推公式遞歸的分類(lèi)通過(guò)做大量的題，根據(jù)遞歸解決不同的問(wèn)題，引申出來(lái)的幾種解決和思考的方式。我們通過(guò)層與層之間的計(jì)算關(guān)系用遞推公式表達(dá)出來(lái)做計(jì)算，經(jīng)過(guò)層層的遞歸，最終得到結(jié)果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言幾個(gè)月之前就想寫(xiě)這樣一篇文章分享給大家，由于自己有心而力不足，沒(méi)有把真...

zhichangterry 2019-08-26 13:50 評(píng)論0 收藏0