網上寫遞歸的文章可以用汗牛充棟來形容了,大多數都非常清晰而又細致的角度上講解了遞歸的概念,原理等等。以前學生的時候,遞歸可以說一直是我的某種死穴,原理,細節(jié)我都懂,但是不管是在如何運用或者如何試試算法題上真是有一種“聽過好多道理,依然過不好這一生的感覺”。經常感覺信心受挫,力不從心吶。但是到后來如果不要去太糾結這些細節(jié),原理反而豁然開朗,突然我發(fā)現我可能是明白了。所以我的這篇瞎扯是想從一個宏觀的角度來扯扯遞歸算法,所以我起了這么個土洋結合的題目,因為全因為的話顯得略裝b,但是我又實在找不到合適而又簡潔的中文來表達“think in”的這個意思。 無論如何,希望看完這篇文章的人不再對遞歸感到混亂,也許能自己運用遞歸解決算法問題或者實際問題,最重要的是希望能幫助一些曾經和我有一樣困惑的人。
雖然是嘴上說的是想重點從宏觀上寫一些如何運用遞歸,但是內心還是想先扯一下遞歸的概念的。遞歸,我雖然沒查到他的最開始的出處,但是我感覺應該不是從計算機這里創(chuàng)造出來的,這兩個字翻譯的也挺傳神,傳遞和歸約,但是如何用好這個傳遞和歸約就是過不好這一生的那一部分了。我一直覺得遞歸的思想頗有點“站在領導層”的感覺,為什么這么說,因為在設計遞歸算法的時候,你只需要設計出大問題化小問題的遞歸算法,很多時候都是簡單的幾個函數就能解決,剩下的具體都交給編譯器或者說語言本身來解決。但是正是這種特性,往往導致我們這種底層人民長期的思維習慣在靈活運用上會有點覺得“這尼瑪就行啦?”或者"還是有點不放心吶“這種感覺,正是這些感覺往往會導致一種混亂,從而舍本求末,造成在靈活運用上的困難。所以,我一直覺得,在設計遞歸算法的時候,要有四步,第一先分析最簡單的情況,第二,從小問題中總結大問題的規(guī)律,第三要寫出偽代碼,然后再寫真的代碼。
我會把遞歸問題分為三大類:
第一類,別細想,想多了絕逼能給你整懵圈型。 這類問題的有兩個特點,一個是定睛一看,按普通算法想感覺完全一下子不知道從哪里下手,第二個就是當你意識到這肯定得用遞歸啊,但是往往你會陷入一個怪圈,在你想出遞歸算法之后,你會自然的去驗證。關鍵是,在你演這個時候或者試著仔細分析這個題目的時候會發(fā)現腦子越來越亂,越來越不夠使,最終本來想的透徹無比的問題就剩文字本身是清晰的了。這類問題比如想這種:
“一個有n階的樓梯,每次可以選擇上一階或者兩階,請問有多少種登頂的方法?” 這個問題是一個爛大街的遞歸問題,如果你不用遞歸的思維去想,會覺得這玩意兒應該怎么弄?但是這個問題使用遞歸的思維大問題化小問題其實很容易就想出解法。先想一階樓梯,兩階樓梯,三階樓梯試試,寫出偽代碼/步驟試試: