所謂遞歸，簡單點來說，就是一個函數直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解。

我們可以把" 遞歸 "比喻成 "查字典 "，當你查一個詞，發現這個詞的解釋中某個詞仍然不懂，于是你開始查這第二個詞。

可惜，第二個詞裡仍然有不懂的詞，于是查第三個詞，這樣查下去，直到有一個詞的解釋是你完全能看懂的，那麼遞歸走到了盡頭，然後你開始後退，逐個明白之前查過的每一個詞，最終，你明白了最開始那個詞的意思。（摘自知乎的一個回答）

我們以階乘作為：

int Factorial(int n){

if (n == 0) return 1;

return

n * Factorial(n - 1);

}

常常聽到 "遞歸的過程就是出入棧的過程"，這句話怎麼理解？我們以上述代碼為例，取 n=3，則過程如下：

·

第 1~4 步，都是入棧過程，Factorial(3)調用了Factorial(2)，Factorial(2)又接着調用Factorial(1)，直到Factorial(0)；

·

·

第 5 步，因 0 是遞歸結束條件，故不再入棧，此時棧高度為 4，即為我們平時所說的遞歸深度；

·

·

第 6~9 步，Factorial(0)做完，出棧，而Factorial(0)做完意味着Factorial(1)也做完，同樣進行出棧，重複下去，直到所有的都出棧完畢，遞歸結束。

·

每一個遞歸程序都可以把它改寫為非遞歸版本。我們隻需利用棧，通過入棧和出棧兩個操作就可以模拟遞歸的過程，二叉樹的遍曆無疑是這方面的代表。

但是并不是每個遞歸程序都是那麼容易被改寫為非遞歸的。某些遞歸程序比較複雜，其入棧和出棧非常繁瑣，給編碼帶來了很大難度，而且易讀性極差，所以條件允許的情況下，推薦使用遞歸。

在初學遞歸的時候, 看到一個遞歸實現, 我們總是難免陷入不停的驗證之中，比如上面提及的階乘，求解Factorial(n)時，我們總會情不自禁的發問，Factorial(n-1)可以求出正确的答案麼？接着我們就會再用Factorial(n-2)去驗證，，，不停地往下驗證直到Factorial(0)。

對遞歸這樣的不适應，和我們平時習慣的思維方式有關。我們習慣的思維是：已知Factorial(0)，乘上 1 就等于Factorial(1)，再乘以 2 就等于Factorial(2)，，，直到乘到 n。

而遞歸和我們的思維方式正好相反。

那我們怎麼判斷這個遞歸計算是否是正确的呢？Paul Graham 提到一種方法，如下：

如果下面這兩點是成立的，我們就知道這個遞歸對于所有的 n 都是正确的。

.

當 n=0,1 時，結果正确；

.

.

假設遞歸對于 n 是正确的，同時對于 n 1 也正确。

.

這種方法很像數學歸納法，也是遞歸正确的思考方式，上述的第 1 點稱為基本情況，第 2 點稱為通用情況。

在遞歸中，我們通常把第 1 點稱為終止條件，因為這樣更容易理解，其作用就是終止遞歸，防止遞歸無限地運行下去。

下面我們用兩個例子來具體說明這種數學歸納法：

例 1 漢諾塔展開目錄

問題描述為：有三根杆子 A，B，C。A 杆上有 N 個穿孔圓盤，盤的尺寸由上到下依次變大，B，C 杆為空。要求按下列規則将所有圓盤移至 C 杆：

.

每次隻能移動一個圓盤；

.

.

大盤不能疊在小盤上面。

.

問：如何移？最少要移動多少次？

首先看下基本情況，即終止條件：N=1 時，直接從 A 移到 C。

再來看下通用情況：當有 N 個圓盤在 A 上，我們已經找到辦法将其移到 C 杠上了，我們怎麼移動 N 1 個圓盤到 C 杠上呢？很簡單，我們首先用将 N 個圓盤移動到 C 上的方法将 N 個圓盤都移動到 B 上，然後再把第 N 1 個圓盤（最後一個）移動到 C 上，再用同樣的方法将在 B 杠上的 N 個圓盤移動到 C 上，問題解決。

代碼如下：

void Hanoi(int n, char a, char b, char c){ //終止條件

if (n == 1)

{

cout <>a <>'-->' <>c <>endl;

return;

} //通用情況

Hanoi(n - 1, a, c, b);

Hanoi(1, a, b, c);

Hanoi(n - 1, b, a, c);

}

例 2 求二叉樹節點個數展開目錄

首先看下基本情況，即終止條件：當為空樹時，節點數為 0；

再來看下通用情況：當前節點的左，右子樹節點數都被求出，則以當前結點為根的二叉樹的節點總數就是 "左子樹 右子樹 1"。

代碼如下：

int Getnodes(Node * node){ //終止條件

if (node == nullptr)

return 0; //通用情況

return

GetNodes(node->left) GetNode(node->right) 1;

}

當我們遇到一個問題時，我們是怎麼判斷該題用遞歸來解決的

問題可用遞歸來解決需具備的條件：

子問題需與原問題為同樣的事，且規模更小

程序停止條件。

遞歸的學習絕對是一個持久戰，沒有人可以一蹴而就。一年兩年的，很尋常。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!