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

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

     我會把遞歸問題分為三大類：

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

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

     1. 如果只有一個階梯，只有一種方法，就是一次性上一階，直接登頂，應該返回1

     2. 如果有兩個階梯，兩種辦法，一次上一階，上兩次，或者一次直接上兩階，應該返回2.

     3. 如果有三個階梯，那么可以選擇1+1+1,1+2，2+1。

     甚至你可以試試4，5，6階數(shù)的樓梯，但是你會發(fā)現(xiàn)的你的腦子到后面根本無法在繼續(xù)思考下去了，會有種大腦不夠用的感覺，這就到了該總結規(guī)律的時候，你會發(fā)現(xiàn)其實你上第n階樓梯的方法數(shù)目就等于你上第n-1階樓梯的方法數(shù)目加上上第n-2方法的數(shù)目，為什么？因為在這兩種情況下，只需要一步你就可以登頂了，在方法的數(shù)目上你已經(jīng)沒得選了。到這里，你會忍不住的想去從細節(jié)上證明你的想法，別控制，你試試按照你的思維走下去。你會想，我靠，這么簡單，真的嗎？我來想想到n-1階的時候是怎樣的呢？你會發(fā)現(xiàn)很快你就會到我上面的那個懵圈狀態(tài)，反過來你會懷疑你的算法是不是對的，這樣你就會掛了。所以，試著僅僅從數(shù)學或者宏觀的角度證明一下這個算法，相信自己也相信計算機。所以這個問題的代碼很簡單，就這么幾行：

photoshop培訓,電腦培訓,電腦維修培訓,移動軟件開發(fā)培訓,網(wǎng)站設計培訓,網(wǎng)站建設培訓 climbStairs

    就是這樣，很多時候用遞歸的方式解決問題寫出的代碼短的超乎想象，所以恐怕這也是造成自我懷疑的一個原因吧。為什么會造成懵圈，我覺得是我們大腦的堆棧不夠大，相比于計算機，在不大的問題規(guī)模上已經(jīng)overflow了。

    類似這樣的稍微復雜但是差不太多的還有：有無限個25美分，10美分，5美分和1美分的硬幣，如何組合成n美分，有多少種兌換方法？ 可以按照我瞎扯的辦法試試，別細想，專注于宏觀設計出的算法本身，嘿嘿。

     第二類，我覺得應該叫”遞歸算法不容易想到“型。 這些問題設計出遞歸算法再反推回去不會造成腦子的懵圈， 但是想出這個遞歸算法容易導致自信心崩潰之類，因為這種問題一般遞歸解法都不太明顯，比如這個吧： 

     ”反轉一個字符串，abcdefg，輸出gfedcba“，又是一個非常常見的問題，這個問題不是很難就能設計出一個一般的解法。利用一個循環(huán)，計算好坐標，利用一個中間變量，相互交換字符的位置，大功告成。但是這個問題完全可以換一種思維，用遞歸的方法去解決。還是先從最小的規(guī)模先試試，還是得先寫下來：

     1. 只有一個字符，直接輸出。

     2. 有兩個字符，交換兩個字符的位置，輸出。

     3. 有三個字符，中間一個字符不變，交換兩邊的字符，輸出。

     4. 有四個字符，前兩個字符互相交換，后兩改字符互相交換，然后兩部分再兩兩交換，輸出。

     5. 有五個字符，中間一個字符不不變，其余的重復4.

    這個算法用寫出每一部分的方法很難總結出規(guī)律，但是如果真的寫出五個字符，在紙上試試，其實很容易就能找到分別交換兩個部分再互相交換的規(guī)律。這可能就是這里面最難的”算法設計“的這個部分吧。所以這個問題寫成代碼大概應該是這樣的：

photoshop培訓,電腦培訓,電腦維修培訓,移動軟件開發(fā)培訓,網(wǎng)站設計培訓,網(wǎng)站建設培訓 reverseString

    這種問題，一般會沮喪在想出這個算法上，但是我覺得其實對于我們這種普通人來說，計算機里的算法設計多還是停留在多見世面才能解決問題的層面。畢竟那種能獨立設計，思考出一個算法的人鳳毛麟角，所以，其實這個時候不必沮喪和失去信心，你現(xiàn)在不知道怎么做可能僅僅是見到的太少，你要見多了，大部分問題都能解決。

    第三類，我把它叫”遞歸才是最好的理解答案思路型“，這種問題最常見于樹啊，圖啊之類的問題，簡直不甚枚舉。特點是，這種問題你會發(fā)現(xiàn)你會自然的用遞歸的思想去思考這個問題，所以說，最后的代碼如果是以遞歸的形式呈現(xiàn)會跟符合人本身的自然思路。 隨便舉一個比較簡單的例子：

      ”計算一個二叉樹所有左葉子節(jié)點的權重值的和"?？粗@個問題思考，思路很容易就流淌出來，一個二叉樹所有左葉子節(jié)點權重值的和就等于一個左子樹的左葉子節(jié)點的權重值加上右子樹的左葉子節(jié)點的權重值?！斑f”的部分很容易就想出來了，那么“歸”的部分就可以從最小的問題思考一下，因為“歸”應該滿足最小的問題集合，假設這個樹只有一個根節(jié)點，那么可能返回0，如果是一個根節(jié)點帶一個左葉子節(jié)點，那么應該返回這個左葉子節(jié)點的值，因為是左葉子節(jié)點的值的和，所以所有的右子樹在這里有可以化為另一個“遞”。貌似有點亂了，列一下可能能清晰一點：

      1. 如果只有根節(jié)點，返回0。

      2. 如果根節(jié)點有左葉子節(jié)點，返回左葉子節(jié)點的值。

      3. 繼續(xù)遍歷根節(jié)點的右子樹。

      4. 遍歷所有當前的左子樹和右子樹，重復1-3。

    這樣再寫成代碼就很容易了：

photoshop培訓,電腦培訓,電腦維修培訓,移動軟件開發(fā)培訓,網(wǎng)站設計培訓,網(wǎng)站建設培訓 sumOfLeftLeaves

    這類問題你會發(fā)現(xiàn)遞歸寫出來的代碼更符合人的自然思維邏輯，比起那些傳統(tǒng)方法可能更容易展開和理解。

 

     好了，上面就是我的一些胡扯，其實就像開頭說的，遞歸主要是"遞“和”歸“，先從宏觀的方面找到傳遞的路子，再用最小的問題集合找到歸約的條件和返回，大部分遞歸問題都很很容易能想出來。如果讓我選一個例子來最初步的理解遞歸算法，我會十分推薦快速排序，你可以就看一遍快速排序的算法描述，然后把它實現(xiàn)出來。不要小看實現(xiàn)一段某某算法，作為工程師，我覺得實現(xiàn)某種算法或者功能比設計算法更符合本職工作，也是一種非常大的能力。就像造汽車的和賽車手，造汽車的不一定開的好車，但是肯定會開車。賽車手大部分都不能獨自制造發(fā)動機，但是肯定懂點基本原理。所以說想不出來算法也并沒有什么好沮喪的。

     最后，希望這篇文章能幫助需要的人。