遞歸是什么?

一、遞歸是什么

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

遞歸有三大要素

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

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

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

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

int f(int n){

}

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

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

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

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

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

int f(int n){

??? if(n == 1){

??????? return 1;

??? }

}

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

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

// 算 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;

??? }

}

第三要素：找出函數(shù)的等價關系式

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

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

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

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

延伸閱讀；

二、遞歸的程序特性

優(yōu)雅性

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

反向性

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

遞推關系

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