一、遞歸是什么

簡單地說，就是如果在函數中存在著調用函數本身的情況，這種現象就叫遞歸。遞歸的基本思想是某個函數直接或者間接地調用自身，這樣原問題的求解就轉換為了許多性質相同但是規模更小的子問題。求解時只需要關注如何把原問題劃分成符合條件的子問題，而不需要過分關注這個子問題是如何被解決的。

遞歸有三大要素

名列前茅要素：明確你這個函數想要干什么

對于遞歸，我覺得很重要的一個事就是，這個函數的功能是什么，他要完成什么樣的一件事，而這個，是完全由你自己來定義的。也就是說，我們先不管函數里面的代碼什么，而是要先明白，你這個函數是要用來干什么。

例如，我定義了一個函數

// 算 n 的階乘(假設n不為0)

int f(int n){

}

這個函數的功能是算 n 的階乘。好了，我們已經定義了一個函數，并且定義了它的功能是什么，接下來我們看第二要素。

第二要素：尋找遞歸結束條件

所謂遞歸，就是會在函數內部代碼中，調用這個函數本身，所以，我們必須要找出遞歸的結束條件，不然的話，會一直調用自己，進入無底洞。也就是說，我們需要找出當參數為啥時，遞歸結束，之后直接把結果返回，請注意，這個時候我們必須能根據這個參數的值，能夠直接知道函數的結果是什么。

例如，上面那個例子，當 n = 1 時，那你應該能夠直接知道 f(n) 是啥吧？此時，f(1) = 1。完善我們函數內部的代碼，把第二要素加進代碼里面，如下

// 算 n 的階乘(假設n不為0)

int f(int n){

??? if(n == 1){

??????? return 1;

??? }

}

有人可能會說，當 n = 2 時，那我們可以直接知道 f(n) 等于多少啊，那我可以把 n = 2 作為遞歸的結束條件嗎？

當然可以，只要你覺得參數是什么時，你能夠直接知道函數的結果，那么你就可以把這個參數作為結束的條件，所以下面這段代碼也是可以的。

// 算 n 的階乘(假設n>=2)

int f(int n){

??? if(n == 2){

??????? return 2;

??? }

}

注意我代碼里面寫的注釋，假設 n >= 2，因為如果 n = 1時，會被漏掉，當 n <= 2時，f(n) = n，所以為了更加嚴謹，我們可以寫成這樣：

// 算 n 的階乘(假設n不為0)

int f(int n){

??? if(n <= 2){

??????? return n;

??? }

}

第三要素：找出函數的等價關系式

第三要素就是，我們要不斷縮小參數的范圍，縮小之后，我們可以通過一些輔助的變量或者操作，使原函數的結果不變。

例如，f(n) 這個范圍比較大，我們可以讓 f(n) = n * f(n-1)。這樣，范圍就由 n 變成了 n-1 了，范圍變小了，并且為了原函數f(n) 不變，我們需要讓 f(n-1) 乘以 n。

說白了，就是要找到原函數的一個等價關系式，f(n) 的等價關系式為 n * f(n-1)，即

f(n) = n * f(n-1)。

延伸閱讀；

二、遞歸的程序特性

優雅性

相比其他解法（比如迭代法），使用遞歸法，你會發現只需少量程序就可描述出解題過程，大大減少了程序的代碼量，而且很好理解。遞歸的能力在于用有限的語句來定義對象的無限集合。

反向性

由于遞歸調用程序需要維護調用棧，而棧（我們在上文提過）具有后進先出的特征，因此遞歸程序適合滿足取反類需求。我們在第五部分有一些編程實踐，比如字符串取反，鏈表取反等相關有趣的算法問題。

遞推關系

遞歸程序可以較明顯的發現遞推關系，反過來也可以這么說，具有遞推關系的問題基本都可以通過遞歸求解（當然也許有性能更佳的解法，但遞歸絕對是一種選擇）。遞推關系常見問題有楊輝三角、階乘計算。