Think in 遞歸

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

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

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

我會(huì)把遞歸問題分為三大類：

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

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

分類導(dǎo)航

Think in 遞歸

延伸閱讀

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