資料結構和演算法面試題系列—遞迴演算法總結
前面總結了隨機演算法，這次再把以前寫的遞迴演算法的文章梳理一下，這篇文章主要是受到宋勁鬆老師寫的《Linux C程式設計》的遞迴章節啟發寫的。最能體現演算法精髓的非遞迴莫屬了，希望這篇文章對初學遞迴或者對遞迴有困惑的朋友們能有所幫助，如有錯誤，也懇請各路大牛指正。二叉樹的遞迴示例程式碼請參見倉庫的 binary_tree 目錄，本文其他程式碼在ofollow,noindex">這裡 。
1 遞迴演算法初探
本段內容主要摘自《linux C一站式程式設計》，作者是宋勁鬆老師，這是我覺得目前看到的國內關於Linux C程式設計
的最好的技術書籍之一，強烈推薦下！
關於遞迴的一個簡單例子是求整數階乘，n!=n*(n-1)!，0!=1
。則可以寫出如下的遞迴程式：
int factorial(int n)
{
if (n == 0)
return 1;
else {
int recurse = factorial(n-1);
int result = n * recurse;
return result;
}
}
複製程式碼
factorial這個函式就是一個遞迴函式，它呼叫了它自己。自己直接或間接呼叫自己的函式稱為遞迴函式。如果覺得迷惑，可以把 factorial(n-1) 這一步看成是在呼叫另一個函式－－另一個有著相同函式名和相同程式碼的函式，呼叫它就是跳到它的程式碼裡執行，然後再返回 factorial(n-1) 這個呼叫的下一步繼續執行。
為了證明遞迴演算法的正確性，我們可以一步步跟進去看執行結果。記得剛學遞迴演算法的時候，老是有丈二和尚摸不著頭腦的感覺，那時候總是想著把遞迴一步步跟進去看執行結果。遞迴層次少還算好辦，但是層次一多，頭就大了，完全不知道自己跟到了遞迴的哪一層。比如求階乘，如果只是factorial(3)跟進去問題還不大，但是若是factorial(100)要跟進去那真的會煩死人。
事實上，我們並不是每個函式都需要跟進去看執行結果的，比如我們在自己的函式中呼叫printf函式時，並沒有鑽進去看它是怎麼列印的，因為我們相信它能完成列印工作。我們在寫factorial函式時有如下程式碼：
int recurse = factorial(n-1); int result = n * recurse; 複製程式碼
這時，如果我們相信factorial是正確的，那麼傳遞引數為n-1它就會返回(n-1)!，那麼result=n*(n-1)!=n!，從而這就是factorial(n)的結果。
當然這有點奇怪：我們還沒寫完factorial這個函式，憑什麼要相信factorial(n-1)是正確的？如果你相信你正在寫的遞迴函式是正確的，並呼叫它，然後在此基礎上寫完這個遞迴函式，那麼它就會是正確的，從而值得你相信它正確。
這麼說還是有點玄乎，我們從數學上嚴格證明一下factorial
函式的正確性。剛才說了，factorial(n)
的正確性依賴於factorial(n-1)
的正確性，只要後者正確，在後者的結果上乘個 n 返回這一步顯然也沒有疑問，那麼我們的函式實現就是正確的。因此要證明factorial(n)
的正確性就是要證明factorial(n-1)
的正確性，同理，要證明factorial(n-1)
的正確性就是要證明factorial(n-2)
的正確性，依此類推下去，最後是：要證明factorial(1)
的正確性就是要證明factorial(0)
的正確性。而factorial(0)
的正確性不依賴於別的函式呼叫，它就是程式中的一個小的分支return 1;
這個 1 是我們根據階乘的定義寫的，肯定是正確的，因此factorial(1)
的實現是正確的，因此factorial(2)
也正確，依此類推，最後factorial(n)
也是正確的。
其實這就是在中學時學的數學歸納法，用數學歸納法來證明只需要證明兩點：Base Case正確，遞推關係正確。寫遞迴函式時一定要記得寫Base Case，否則即使遞推關係正確，整個函式也不正確。如果 factorial 函式漏掉了Base Case，那麼會導致無限迴圈。
2 遞迴經典問題
從上一節的一個關於求階乘的簡單例子的論述，我們可以瞭解到遞迴演算法的精髓：要從功能上理解函式，同時你要相信你正在寫的函式是正確的，在此基礎上呼叫它，那麼它就是正確的。 下面就從幾個常見的演算法題來看看如何理解遞迴，這是我的一些理解，歡迎大家提出更好的方法。
2.1）漢諾塔問題
題：漢諾塔問題是個常見問題，就是說有n個大小不等的盤子放在一個塔A上面，自底向上按照從小到大的順序排列。要求將所有n個盤子搬到另一個塔C上面，可以藉助一個塔B中轉，但是要滿足任何時刻大盤子不能放在小盤子上面。
解：基本思想分三步，先把上面的 N-1 個盤子經 C 移到 B，然後將最底下的盤子移到 C，再將 B 上面的N-1個盤子經 A 移動到 C。總的時間複雜度f(n)=2f(n-1)+1
，所以f(n)=2^n-1
。
/**
* 漢諾塔
*/
void hano(char a, char b, char c, int n) {
if (n <= 0) return;
hano(a, c, b, n-1);
move(a, c);
hano(b, a, c, n-1);
}
void move(char a, char b)
{
printf("%c->%c\n", a, b);
}
複製程式碼
2.2）求二叉樹的深度
這裡的深度指的是二叉樹從根結點到葉結點最大的高度，比如只有一個結點，則深度為1，如果有N層，則高度為N。
int depth(BTNode* root)
{
if (root == NULL)
return 0;
else {
int lDepth = depth(root->left);//獲取左子樹深度
int rDepth = depth(root->right); //獲取右子樹深度
return lDepth>rDepth? lDepth+1: rDepth+1; //取較大值+1即為二叉樹深度
}
}
複製程式碼
那麼如何從功能上理解depth
函式呢？我們可以知道定義該函式的目的就是求二叉樹深度，也就是說我們要是完成了函式depth
，那麼depth(root)
就能正確返回以 root 為根結點的二叉樹的深度。因此我們的程式碼中depth(root->left)
返回左子樹的深度，而depth(root->right)
返回右子樹的深度。儘管這個時候我們還沒有寫完depth
函式，但是我們相信depth
函式能夠正確完成功能。因此我們得到了lDepth
和rDepth
，而後通過比較返回較大值加1為二叉樹的深度。
如果不好理解，可以想象在 depth 中呼叫的函式 depth(root->left) 為另外一個同樣名字完成相同功能的函式，這樣就好理解了。注意 Base Case，這裡就是當 root==NULL 時，則深度為0，函式返回0。
2.3）判斷二叉樹是否平衡
一顆平衡的二叉樹是指其任意結點的左右子樹深度之差不大於1。判斷一棵二叉樹是否是平衡的，可以使用遞迴演算法來實現。
int isBalanceBTTop2Down(BTNode *root)
{
if (!root) return 1;
int leftHeight = btHeight(root->left);
int rightHeight = btHeight(root->right);
int hDiff = abs(leftHeight - rightHeight);
if (hDiff > 1) return 0;
return isBalanceBTTop2Down(root->left) && isBalanceBTTop2Down(root->right);
}
複製程式碼
該函式的功能定義是二叉樹 root 是平衡二叉樹，即它所有結點的左右子樹深度之差不大於1。首先判斷根結點是否滿足條件，如果不滿足，則直接返回 0。如果滿足，則需要判斷左子樹和右子樹是否都是平衡二叉樹，若都是則返回1，否則0。
2.4）排列演算法
排列演算法也是遞迴的典範，記得當初第一次看時一層層跟程式碼，頭都大了，現在從函式功能上來看確實好理解多了。先看程式碼：
/**
* 輸出全排列，k為起始位置，n為陣列大小
*/
void permute(int a[], int k, int n)
{
if (k == n-1) {
printIntArray(a, n); // 輸出陣列
} else {
int i;
for (i = k; i < n; i++) {
swapInt(a, i, k); // 交換
permute(a, k+1, n); // 下一次排列
swapInt(a, i, k); // 恢復原來的序列
}
}
}
複製程式碼
首先明確的是perm(a, k, n)
函式的功能:輸出陣列 a 從位置 k 開始的所有排列，陣列長度為 n。這樣我們在呼叫程式的時候，呼叫格式為perm(a, 0, n)
，即輸出陣列從位置 0 開始的所有排列，也就是該陣列的所有排列。基礎條件是k==n-1
，此時已經到達最後一個元素，一次排列已經完成，直接輸出。否則，從位置k開始的每個元素都與位置k的值交換(包括自己與自己交換)，然後進行下一次排列，排列完成後記得恢復原來的序列。
假定陣列a大小N=3，則程式呼叫 perm(a, 0, 3) 可以如下理解： 第一次交換 0，0，並執行perm(a, 1, 3)，執行完再次交換0，0，陣列此時又恢復成初始值。 第二次交換 1，0（注意陣列此時是初始值），並執行perm(a, 1, 3), 執行完再次交換1，0，陣列此時又恢復成初始值。 第三次交換 2，0，並執行perm(a, 1, 3)，執行完成後交換2，0，陣列恢復成初始值。
也就是說，從功能上看，首先確定第0個位置，然後呼叫perm(a, 1, 3)輸出從1開始的排列，這樣就可以輸出所有排列。而第0個位置可能的值為a[0], a[1],a[2]，這通過交換來保證第0個位置可能出現的值，記得每次交換後要恢復初始值。
如陣列a={1,2,3}
，則程式執行輸出結果為：1 2 3 ，1 3 2 ，2 1 3 ，2 3 1 ，3 2 1 ，3 1 2
。即先輸出以1為排列第一個值的排列，而後是2和3為第一個值的排列。
2.5）組合演算法
組合演算法也可以用遞迴實現，只是它的原理跟0-1揹包問題類似。即要麼選要麼不選，注意不能選重複的數。完整程式碼如下：
/*
* 組合主函式，包括選取1到n個數字
*/
void combination(int a[], int n)
{
int *select = (int *)calloc(sizeof(int), n); // select為輔助陣列，用於儲存選取的數
int k;
for (k = 1; k <= n; k++) {
combinationUtil(a, n, 0, k, select);
}
}
/*
* 組合工具函式：從陣列a從位置i開始選取k個數
*/
void combinationUtil(int a[], int n, int i, int k, int *select)
{
if (i > n) return; //位置超出陣列範圍直接返回，否則非法訪問會出段錯誤
if (k == 0) {//選取完了，輸出選取的數字
int j;
for (j = 0; j < n; j++) {
if (select[j])
printf("%d ", a[j]);
}
printf("\n");
} else {
select[i] = 1;
combinationUtil(a, n, i+1, k-1, select); //第i個數字被選取，從後續i+1開始選取k-1個數
select[i] = 0;
combinationUtil(a, n, i+1, k, select); //第i個數字不選，則從後續i+1位置開始還要選取k個數
}
}
複製程式碼
2.6) 逆序列印字串
這個比較簡單，程式碼如下：
void reversePrint(const char *str)
{
if (!*str)
return;
reversePrint(str + 1);
putchar(*str);
}
複製程式碼
2.7) 連結串列逆序
連結串列逆序通常我們會用迭代的方式實現，但是如果要顯得特立獨行一點，可以使用遞迴，如下，程式碼請見倉庫的aslist
目錄。
/**
* 連結串列逆序，遞迴實現。
*/
ListNode *listReverseRecursive(ListNode *head)
{
if (!head || !head->next) {
return head;
}
ListNode *reversedHead = listReverseRecursive(head->next);
head->next->next = head;
head->next = NULL;
return reversedHead;
}
複製程式碼