一、遞歸是什么

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

遞歸有三大要素

名列前茅要素：明確你這個(gè)函數(shù)想要干什么

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

例如，我定義了一個(gè)函數(shù)

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

int f(int n){

}

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

第二要素：尋找遞歸結(jié)束條件

所謂遞歸，就是會(huì)在函數(shù)內(nèi)部代碼中，調(diào)用這個(gè)函數(shù)本身，所以，我們必須要找出遞歸的結(jié)束條件，不然的話，會(huì)一直調(diào)用自己，進(jìn)入無底洞。也就是說，我們需要找出當(dāng)參數(shù)為啥時(shí)，遞歸結(jié)束，之后直接把結(jié)果返回，請(qǐng)注意，這個(gè)時(shí)候我們必須能根據(jù)這個(gè)參數(shù)的值，能夠直接知道函數(shù)的結(jié)果是什么。

例如，上面那個(gè)例子，當(dāng) n = 1 時(shí)，那你應(yīng)該能夠直接知道 f(n) 是啥吧？此時(shí)，f(1) = 1。完善我們函數(shù)內(nèi)部的代碼，把第二要素加進(jìn)代碼里面，如下

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

int f(int n){

??? if(n == 1){

??????? return 1;

??? }

}

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

當(dāng)然可以，只要你覺得參數(shù)是什么時(shí)，你能夠直接知道函數(shù)的結(jié)果，那么你就可以把這個(gè)參數(shù)作為結(jié)束的條件，所以下面這段代碼也是可以的。

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

int f(int n){

??? if(n == 2){

??????? return 2;

??? }

}

注意我代碼里面寫的注釋，假設(shè) n >= 2，因?yàn)槿绻?n = 1時(shí)，會(huì)被漏掉，當(dāng) n <= 2時(shí)，f(n) = n，所以為了更加嚴(yán)謹(jǐn)，我們可以寫成這樣：

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

int f(int n){

??? if(n <= 2){

??????? return n;

??? }

}

第三要素：找出函數(shù)的等價(jià)關(guān)系式

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

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

說白了，就是要找到原函數(shù)的一個(gè)等價(jià)關(guān)系式，f(n) 的等價(jià)關(guān)系式為 n * f(n-1)，即

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

延伸閱讀；

二、遞歸的程序特性

優(yōu)雅性

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

反向性

由于遞歸調(diào)用程序需要維護(hù)調(diào)用棧，而棧（我們?cè)谏衔奶徇^）具有后進(jìn)先出的特征，因此遞歸程序適合滿足取反類需求。我們?cè)诘谖宀糠钟幸恍┚幊虒?shí)踐，比如字符串取反，鏈表取反等相關(guān)有趣的算法問題。

遞推關(guān)系

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