Think in 遞歸

發(fā)布時(shí)間：2017年03月01日作者：文章轉(zhuǎn)自網(wǎng)絡(luò)，版權(quán)歸原作者所有，反饋可立刻刪除 (該文來(lái)自筆記，點(diǎn)擊查看原文)

網(wǎng)上寫(xiě)遞歸的文章可以用汗牛充棟來(lái)形容了，大多數(shù)都非常清晰而又細(xì)致的角度上講解了遞歸的概念，原理等等。以前學(xué)生的時(shí)候，遞歸可以說(shuō)一直是我的某種死穴，原理，細(xì)節(jié)我都懂，但是不管是在如何運(yùn)用或者如何試試算法題上真是有一種“聽(tīng)過(guò)好多道理，依然過(guò)不好這一生的感覺(jué)”。經(jīng)常感覺(jué)信心受挫，力不從心吶。但是到后來(lái)如果不要去太糾結(jié)這些細(xì)節(jié)，原理反而豁然開(kāi)朗，突然我發(fā)現(xiàn)我可能是明白了。所以我的這篇瞎扯是想從一個(gè)宏觀的角度來(lái)扯扯遞歸算法，所以我起了這么個(gè)土洋結(jié)合的題目，因?yàn)槿驗(yàn)榈脑掞@得略裝b，但是我又實(shí)在找不到合適而又簡(jiǎn)潔的中文來(lái)表達(dá)“think in”的這個(gè)意思。無(wú)論如何，希望看完這篇文章的人不再對(duì)遞歸感到混亂，也許能自己運(yùn)用遞歸解決算法問(wèn)題或者實(shí)際問(wèn)題，最重要的是希望能幫助一些曾經(jīng)和我有一樣困惑的人。

雖然是嘴上說(shuō)的是想重點(diǎn)從宏觀上寫(xiě)一些如何運(yùn)用遞歸，但是內(nèi)心還是想先扯一下遞歸的概念的。遞歸，我雖然沒(méi)查到他的最開(kāi)始的出處，但是我感覺(jué)應(yīng)該不是從計(jì)算機(jī)這里創(chuàng)造出來(lái)的，這兩個(gè)字翻譯的也挺傳神，傳遞和歸約，但是如何用好這個(gè)傳遞和歸約就是過(guò)不好這一生的那一部分了。我一直覺(jué)得遞歸的思想頗有點(diǎn)“站在領(lǐng)導(dǎo)層”的感覺(jué)，為什么這么說(shuō)，因?yàn)樵谠O(shè)計(jì)遞歸算法的時(shí)候，你只需要設(shè)計(jì)出大問(wèn)題化小問(wèn)題的遞歸算法，很多時(shí)候都是簡(jiǎn)單的幾個(gè)函數(shù)就能解決，剩下的具體都交給編譯器或者說(shuō)語(yǔ)言本身來(lái)解決。但是正是這種特性，往往導(dǎo)致我們這種底層人民長(zhǎng)期的思維習(xí)慣在靈活運(yùn)用上會(huì)有點(diǎn)覺(jué)得“這尼瑪就行啦？”或者"還是有點(diǎn)不放心吶“這種感覺(jué)，正是這些感覺(jué)往往會(huì)導(dǎo)致一種混亂，從而舍本求末，造成在靈活運(yùn)用上的困難。所以，我一直覺(jué)得，在設(shè)計(jì)遞歸算法的時(shí)候，要有四步，第一先分析最簡(jiǎn)單的情況，第二，從小問(wèn)題中總結(jié)大問(wèn)題的規(guī)律，第三要寫(xiě)出偽代碼，然后再寫(xiě)真的代碼。

我會(huì)把遞歸問(wèn)題分為三大類(lèi)：

第一類(lèi)，別細(xì)想，想多了絕逼能給你整懵圈型。這類(lèi)問(wèn)題的有兩個(gè)特點(diǎn)，一個(gè)是定睛一看，按普通算法想感覺(jué)完全一下子不知道從哪里下手，第二個(gè)就是當(dāng)你意識(shí)到這肯定得用遞歸啊，但是往往你會(huì)陷入一個(gè)怪圈，在你想出遞歸算法之后，你會(huì)自然的去驗(yàn)證。關(guān)鍵是，在你演這個(gè)時(shí)候或者試著仔細(xì)分析這個(gè)題目的時(shí)候會(huì)發(fā)現(xiàn)腦子越來(lái)越亂，越來(lái)越不夠使，最終本來(lái)想的透徹?zé)o比的問(wèn)題就剩文字本身是清晰的了。這類(lèi)問(wèn)題比如想這種：

“一個(gè)有n階的樓梯，每次可以選擇上一階或者兩階，請(qǐng)問(wèn)有多少種登頂?shù)姆椒?？?這個(gè)問(wèn)題是一個(gè)爛大街的遞歸問(wèn)題，如果你不用遞歸的思維去想，會(huì)覺(jué)得這玩意兒應(yīng)該怎么弄？但是這個(gè)問(wèn)題使用遞歸的思維大問(wèn)題化小問(wèn)題其實(shí)很容易就想出解法。先想一階樓梯，兩階樓梯，三階樓梯試試，寫(xiě)出偽代碼/步驟試試：

分類(lèi)導(dǎo)航

Think in 遞歸

延伸閱讀

我想了解如何學(xué)習(xí)