本文來自“天狼嘯幽月”的投稿，已獲獨家授權
關于設計遞歸函數，個人有一點總結和心得，和大家分享一下。
從一個簡單的例子開始
#include "stdio.h"
運作結果是：
我們注意到，函數fun裡面調用了一個函數fun，也就是調用了自己，這種函數調用自己的技巧我們就稱為遞歸算法，而這個調用了自己的函數fun就是一個遞歸函數。
函數fun的運作過程是這樣的：
大家在設計遞歸函數時，可能也會像上圖這樣去思考每一層的變化，這樣一來往往讓人頭大。
其實，根本不用這樣，設計遞歸函數其實很簡單，基本上隻考慮它的第一層就可以了，設計它甚至比設計普通的函數還要簡單，因為它有便利之處(後面會講到)。
但是，要做到這樣，還需要一些了解上的技巧，我會詳細給大家講明。
為了說明友善，函數fun和它調用的fun我們要分開稱呼，外層的fun稱作1号fun，被1号調用的fun就稱為2号fun，如果調用了多個fun，就3号、4号這樣順延；而如果遇到要按上面的遞歸結構說明更深層的fun的情況，取名也這樣順延。
回頭來解析本例，如何寫出這個遞歸函數。
1. 首先我們要想，函數fun應該設計成一個怎樣的功能？這是最重要的一環。
主要看需求，滿足需求的情況下微調即可。
比如我們的需求是求n以内的自然數之和，那麼我們就這樣設計fun的功能——給予正整數n，傳回n及以内的自然數之和。
函數功能設計(決定)好之後，那麼要得到10以内的自然數之和也就很簡單了，是以main裡通過fun( 10 ) 就能得到答案了。
2. 制定了功能後，接着就要實作功能了。
作為遞歸函數，需要調用自己，調用時隻需當它是一個普通函數就行，因為它的參數、傳回值、功能等都已明确，不用去想它還沒實作這件事，普通函數怎麼用它就怎麼用。
但是，有個小問題，按這個思路，fun最簡單的實作應該是這樣：
畢竟根據fun的功能，直接調用fun( n ) 就能得到結果了，然後将結果傳回不就實作本函數了嗎？
哈哈，這樣會死循環，剛剛的方法還不夠，需要加點限制——在“當做一個普通函數來用”這個思路的基礎上，加上“不能原封不動地把自己的參數給它”。
比如fun首先會收到10，那麼它調用2号fun時，就不能給它10，至少要改變一點。
同樣的，如果1号fun收到的是a、b、c，那麼調用2号fun時就不能給a、b、c，稍微改變一點，比如給a-1、b、c。
受到這條限制後，最簡單的實作方法就變成了：
這個方法也就是讓自己隻計算最簡單的一部分，剩下的任務全交給2号去做。
當然，根據這個理論，實作的方法太多了，這樣也是可以的
這仍然是“自己隻計算一點點，剩下的全交給2号去做”的思路，隻是比起上一個，這次1号計算的稍微多了一點而已。
3. 想辦法結束遞歸。
遞歸也是一種循環，循環語句尚且有結束循環的條件，遞歸當然也應該有。
不過需要注意的是，這個結束的條件需要放在調用2号之前，因為如果不這樣做的話，仍然是無休止遞歸，控制流始終無法到達結束條件這裡。
那麼，如何寫結束條件呢？可以分兩種情況來考慮，一種是按最簡的方法實作的，此時基本考慮最簡單的情況即可；當實作不是最簡時，情況要考慮多點。
最簡的實作方法如下：
那麼此時最簡單的情況就是n為1，結束條件就這樣寫：
當然，你可能覺得最簡單的情況是n為0，這也可以(不過根據需求，最簡情況理應是1)：
下面是沒按最簡方式來實作的方案：
這時再用n==1(或n==0)來作為結束條件就有漏洞了，比如當n為2時，傳給2号fun的是0，n無法經過1，死循環。
此時的方法稍複雜點——
根據收到的參數與給2号的參數的差來考慮結束條件
(簡單來說就是讓1号和2号的參數銜接，不要出現斷層)
以及從遞歸結構的尾端的角度來驗證正确性
(簡單來說就是去測試幾個邊緣值看會不會死循環)。
概括就是根據參數設條件，以及驗證。
比如fun收到的是n，傳給2号的是n-2，中間少了n-1，那麼1号fun就應該考慮n和n-1兩種最簡的情況，比如我們可以認為n為1或0時最簡：
也可以認為n為1和2時最簡：
接下來是驗證環節，測試幾個值看看會不會有缺漏，不然又會是死循環。
假如n為5(取值随意，不放心就稍微取寬泛點)，則2号得到n=3，3号得到n=1，3号收到的1遇到結束條件而正确傳回。
假如n為4，則2号得到n=2，會遇到結束條件而正确傳回。
假如n為3，則2号得到n=1，會遇到結束條件而正确傳回。
假如n為2，遇到結束條件而正确傳回。
假如n為1，遇到結束條件而正确傳回。
隻要調用時不亂來，那麼目前就驗證完畢。
而如果擔心n的參數為0或負數等錯誤情況，另加一個結束條件即可：
至此，基本方法已經說明完畢，我們做個歸納總結：
1. 設定好函數的功能(包括參數和傳回值的設計)，這是最關鍵的一環。
2. 将自身作為一個普通函數來調用，認定它能完成它的工作。
3. 調用自身時給的參數不能和自己的完全相同。
4. 将一個最簡單的情況作為結束條件，放在調用自身之前。
5. 檢查結束條件是否有疏漏。
如果對這個過程和理論還不能了解，可以借助這個小故事：
main想要用fun來求n以内的自然數之和，但函數fun就想，诶呀好麻煩呀，趕緊應付應付得了，搞完回家喝喝小酒才是生活呀，該怎麼應付呢，诶，有了，我知道有個叫fun的函數，它可以計算n以内的自然數之和，讓它來搞就好了嘿嘿嘿，诶，等等，它的名字怎麼這麼眼熟呢，唉，不管了，就讓它幫我計算1～10的和好了，诶呀，突然才想起，主上大人給我制定過一條規則——“調用它時給的參數不能和自己的完全相同”，上有政策，下有對策，main給我10，既然規定我不能把10給fun的話，那我就給9，把它的計算結果再加個10就可以交差了，嘻嘻嘻，聰明如我。
fun完成了工作正回家呢，突然眼前景色一閃，它回到了工作的地方并收到通知——計算1～9的和。是不是喝酒喝太多眼花了，不管了，先把工作完成再說。它故技重施，偷懶用2号計算1～8的和，自己把結果再加上9交差。
fun又回家了，然後它又突然回到了工作的地方，fun開始覺得不對勁了，工作的時候努力回想前因後果，它終于想起，它使喚的函數fun不正是自己嗎？原來讓自己回來工作的，就是過去的自己！
既然發現了問題就要想辦法阻止，可是自己偷懶慣了，未來的自己也不是現在的自己，幹脆還是像以前一樣交給未來的自己幹吧，不過為了防止自己永無止境地幹下去，必須要設一個結束條件。
既然計算的是1～n的和，那麼n最後就是1，讓最後計算1的自己不要再偷懶使喚别的函數就可以了。結束條件寫哪裡呢？這時fun又想起了主上大人制定的規則——“結束條件要放在調用自身前”，不愧是傳說中的主上大人，原來他已經知曉一切，fun在心裡對主上肅然起敬。
學習了方法後，接下來我們通過兩個例子來驗證成果——漢諾塔、反轉連結清單。
漢諾塔問題
漢諾塔是一個遊戲，遊戲規則如下：
如圖有A、B、C三根柱子，A柱子上有一些疊起來的圓盤，大的在下，小的在上，現在要把圓盤都轉移到C柱上，移動規則是：
1. 每次移動一個圓盤到另一根柱子上；
2. 大的盤子不能在小的上面。
(這種遊戲網上很多，可以先試玩看看)
題目是：指定A柱子上的圓盤數，移動到C柱子上，程式應顯示圓盤在柱子間的移動過程。
老規矩
一：設計函數功能。
題目要求把n個圓盤從A柱子移到C柱子，那我們就把函數的功能設計為——把n個圓盤從某根柱子移動到另一根柱子上并顯示移動過程。
函數原型設為void hanoi( int n, char a, char b, char c )
a表示初始情況圓盤所在的柱子
c表示要轉移的柱子
b表示用來中轉的柱子
n表示a柱子上的圓盤數
三個char變量存儲的是三根柱子的名字。
函數功能設計好後，那麼main要得到從'A'柱移動10個圓盤到'C'柱的過程，隻需一行即可—— hanoi ( 10 , 'A' , 'B' , 'C' )
二：實作函數功能
依照hanoi的功能，可以讓它移動n-1個盤子，自己則移動剩下的一個，于是我們隻需三步即可完成這個過程：
第一步，讓2号hanoi移動n-1個圓盤到B柱子。
由于對1号來說，a是自己的起始柱，b是中轉柱，c是目标柱，是以它要讓2号把盤子從a移動到b，是以調用hanoi( n-1 , a , c , b ) ，也就是對2号來說，1号的b柱就是它的目标柱。效果如下：
第二步，1号将一個圓盤從A盤移動到C槽。
由于實際上并沒有什麼盤子的資料，是以輸出移動過程就是在移動盤子了——printf("%c--->%c\n", a, c) ，它表示将起始a柱的一個圓盤移動到目标c柱：
第三步，2号将b柱上n-1個圓盤移動到c柱上——調用hanoi( n-1 , b, a, c ) ，結果如下：
三. 結束條件：
當圓盤數為1就是最簡情況
if(n==
得出代碼：
#include "stdio.h" return 0;
}
四. 檢查：
由于n==1是結束條件，而n在調用時都是按1遞減，是以當n大于1時，n最終都會變成1而結束，不考慮n為負數或0這種錯誤的情況，已正确實作。
對此方法的思考
你們可能會覺得荒誕—— 2号能讓n-1個圓盤直接轉移？難道可以無視“一次移動一個”和“大的在上小的在下”這些規則？何等荒謬！怎麼做到的？
這正是此方法的魅力，也正是前面說的“更便利”的所在。
如果不按遞歸來寫，那會很複雜，而按這種思路的遞歸來寫，直接憑空得到了一個大幫手——一個叫hanoi的函數，它能完成n個盤子的轉移，簡直就像配備了一個完美的API，它總是能剛好滿足我們的需求，要不是有一個規則限制(調用時不能給出一樣的參數)，任務甚至簡單到直接調用它就完成了，而即便有這個限制，也不過是讓我們實作最簡單的一層，其餘更複雜的事務全交給這個“API”去完成了，還有比這更完美和簡單的事嗎？
這也難怪大家會覺得不可思議、無法了解，畢竟天底下哪有這樣的好事，但它确實實作了，那麼我們也不得不承認——遞歸算法是何等高明和美妙！
但有個問題還是要解釋的——為什麼這麼簡單無腦的方法真的可以實作？
前面說過，遞歸也是一種循環，循環就是重複，說明不同層的遞歸函數仍然是高度相似的，它們都是在完成一個相同的任務，也就是說，這個任務我們隻要實作一次就行了，就像循環語句裡的循環體，而我們也确實把這個單次的任務的實作寫出來了，也就是2号做的事務之外，由我們實作的那最簡單的一層。
是以，“調用時不能給出完全相同的參數”這個規則，除了防止無限遞歸外，也是在讓你去實作一個基本的步驟，而遞歸的實作，不過就是在不斷循環這個步驟罷了。
這個方法基本上可以适應絕大多數遞歸算法，不過，有些情況可能需要稍稍注意，設計遞歸函數時，我們總是需要各種參數，但是第一次調用時(比如main對該函數的調用)卻不一定喜歡給這些參數，比如漢諾塔，目前為止幾乎所有的漢諾塔遊戲都是從A柱轉移到C柱，這幾乎是預設的，那麼調用時隻需給出盤子數才是最簡潔友善的設計，但遞歸函數的參數顯然不能這麼設計，不然沒法遞歸了，對于這種情況，我們可以将對遞歸函數的調用包裝一次，就像這樣：
void view_hanoi( int n ) return 0;
}
反轉連結清單
本次我們改變順序，先展示代碼，然後解讀代碼：
#include "stdio.h"
本例使用了3個遞歸函數——遞歸建立連結清單、遞歸釋放連結清單、遞歸反轉連結清單，接下來分别解析。
遞歸建立連結清單——create函數
功能：指定生成的結點數量(給予參數)，傳回頭結點的位址。
實作：先建立了一個結點作為頭結點并設定資料後，用2号建立num-1個結點的連結清單，傳回它第一個結點的位址給頭結點的next指針，于是建立完畢，傳回頭結點p的位址。
結束條件：考慮到參數是遞減1傳遞，那麼肯定會經過0，于是當num==0時傳回NULL，考慮到錯誤情況，是以設定結束條件num<=0。
遞歸釋放連結清單——my_free函數
功能：給予頭結點的位址，釋放該連結清單。
實作：先調用2号釋放從第二個結點開始的連結清單，也就是把除頭結點外剩下的結點釋放了，然後釋放頭結點。
結束條件：連結清單逐點傳遞，會經過連結清單尾，設尾端NULL為結束條件。
需要注意的是，這個過程不能反過來，比如像這樣：
free( p );
my_free( p->next );
如果p釋放了，p->next的值也就沒有了，這不是遞歸和本方法的問題，站在普通調用的角度來看也是這個情況。當然，如果你硬要這樣做也有辦法：
struct node* t = p->next;
free( p );
my_free( t );
遞歸反轉連結清單——reverse函數
功能：給予頭結點的位址，反轉連結清單，傳回新的頭結點的位址。
實作：先調用2号，讓它把第二個結點開始的連結清單反轉，得到反轉後連結清單的頭結點head，然後将原本的頭結點p放到連結清單尾端，傳回頭結點的位址head。
這個過程略有點繞，我們用圖來說明，首先是原連結清單的樣子：
先将p結點之後的連結清單(也就是從結點9開始的連結清單)反轉，頭結點也就變為了1(建立head來儲存頭結點位址)，而由于結點p沒有變化，是以p的下一個結點依然是9：
由于結點p的問題，整個連結清單還沒完全反轉，是以再做幾個操作——讓結點9的next指向p(即p成為結尾)，p的next指向NULL：
如此，連結清單反轉完畢，傳回head。
結束條件：當結點隻有一個時是最簡情況(p==NULL是排除錯誤情況)，判斷是否隻有一個結點的方法是看它的next指針是否為NULL。
從另一方面來看，實作的方法中，p->next->next必須保證p->next不為空，即至少是在有兩個結點的情況下進行的反轉，是以結束條件設為1個。
這個思路的一個難點就是要想清楚如何把頭結點p放到連結清單的結尾，你可以從頭結點周遊，但其實完全沒必要，既然是反轉的話，第二個結點就會成為倒數第二個結點，p的内容一直沒變過，是以可以直接找到結點9，兩次指派操作就能讓它成為尾結點。
結語
關于遞歸的例子就講解到這裡吧。
如果面對的是較長的遞歸函數，也無需驚慌，按照我們設定的步驟操作就行了
首先将函數功能明确，以快速排序和歸并排序為例，雖然都需要遞歸，但排序的算法不一樣，這個時候設計函數功能就需要包含具體的排序方式，如果在設計功能時僅說明是排序的話，那麼實作時就無從下手，因為用遞歸實作排序的方法有很多種；
接着根據設計的功能去實作，利用自己(2号)，實作一遍單層的邏輯，如果代碼較長，說明你可能沒有實作最簡方案，或者它确實比較複雜，以至于實作單層就需要較多代碼，比如tree指令的實作。
往期 精彩回顧
我是一個線程
我是一個Java Class
面向對象聖經
函數式程式設計聖經
TCP/IP之大明郵差
CPU阿甘
我是一個網卡
我是一個路由器
一個故事講完HTTPs
程式設計語言的巅峰
Java：一個帝國的誕生
JavaScript：一個屌絲的逆襲
負載均衡的原理
閱讀源碼的三種境界