之前分享了一篇隨機算法，這次再把以前寫的遞歸算法的文章梳理一下，這篇文章主要是受到宋勁松老師寫的《Linux C編程》的遞歸章節(jié)啟發(fā)寫的。最能體現(xiàn)算法精髓的非遞歸莫屬了，希望這篇文章對初學(xué)遞歸或者對遞歸不甚了解的筒子們能有所幫助，也懇請各路大牛指正。

1 遞歸算法初探

本段內(nèi)容大部分摘自《linux C一站式編程》，作者是宋勁松老師，我認為這是目前看到的國內(nèi)關(guān)于linux C編程的最好的一本技術(shù)書籍，強烈推薦！

關(guān)于遞歸的一個簡單例子是求整數(shù)階乘，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這個函數(shù)就是一個遞歸函數(shù)，它調(diào)用了它自己。自己直接或間接調(diào)用自己的函數(shù)稱為遞歸函數(shù)。如果覺得迷惑，可以把factorial(n-1)這一步看成是在調(diào)用另一個函數(shù)－－另一個有著相同函數(shù)名和相同代碼的函數(shù)，調(diào)用它就是跳到它的代碼里執(zhí)行，然后再返回factorial(n-1)這個調(diào)用的下一步繼續(xù)執(zhí)行。

為了證明遞歸算法的正確性，我們可以一步步跟進去看執(zhí)行結(jié)果。記得剛學(xué)遞歸算法的時候，老是有丈二和尚摸不著頭腦的感覺，那時候總是想著把遞歸一步步跟進去看執(zhí)行結(jié)果。遞歸層次少還算好辦，但是層次一多，頭就大了，完全不知道自己跟到了遞歸的哪一層。比如求階乘，如果只是factorial(3)跟進去問題還不大，但是若是factorial(100)要跟進去那真的會煩死人。

事實上，我們并不是每個函數(shù)都需要跟進去看執(zhí)行結(jié)果的，比如我們在自己的函數(shù)中調(diào)用printf函數(shù)時，并沒有鉆進去看它是怎么打印的，因為我們相信它能完成打印工作。我們在寫factorial函數(shù)時有如下代碼：

...
int recurse = factorial(n-1);
int result = n * recurse;
...

這時，如果我們相信factorial是正確的，那么傳遞參數(shù)為n-1它就會返回(n-1)!，那么result=n*(n-1)!=n!，從而這就是factorial(n)的結(jié)果。

當(dāng)然這有點奇怪：我們還沒寫完factorial這個函數(shù)，憑什么要相信factorial(n-1)是正確的？如果你相信你正在寫的遞歸函數(shù)是正確的，并調(diào)用它，然后在此基礎(chǔ)上寫完這個遞歸函數(shù)，那么它就會是正確的，從而值得你相信它正確。

這么說還是有點玄乎，我們從數(shù)學(xué)上嚴格證明一下factorial函數(shù)的正確性。剛才說了，factorial(n)的正確性依賴于factorial(n-1)的正確性，只要后者正確，在后者的結(jié)果上乘個n返回這一步顯然也沒有疑問，那么我們的函數(shù)實現(xiàn)就是正確的。因此要證明factorial(n)的正確性就是要證明factorial(n-1)的正確性，同理，要證明factorial(n-1)的正確性就是要證明factorial(n-2)的正確性，依此類推下去，最后是：要證明factorial(1)的正確性就是要證明factorial(0)的正確性。而factorial(0)的正確性不依賴于別的函數(shù)調(diào)用，它就是程序中的一個小的分支return 1;這個1是我們根據(jù)階乘的定義寫的，肯定是正確的，因此factorial(1)的實現(xiàn)是正確的，因此factorial(2)也正確，依此類推，最后factorial(n)也是正確的。

其實這就是在中學(xué)時學(xué)的數(shù)學(xué)歸納法，用數(shù)學(xué)歸納法來證明只需要證明兩點：Base Case正確，遞推關(guān)系正確。寫遞歸函數(shù)時一定要記得寫B(tài)ase Case，否則即使遞推關(guān)系正確，整個函數(shù)也不正確。如果factorial函數(shù)漏掉了Base Case，那么會導(dǎo)致無限循環(huán)。

2 遞歸經(jīng)典問題

從上一節(jié)的一個關(guān)于求階乘的簡單例子的論述，我們可以了解到遞歸算法的精髓：要從功能上理解函數(shù)，同時你要相信你正在寫的函數(shù)是正確的，在此基礎(chǔ)上調(diào)用它，那么它就是正確的。下面就從幾個常見的算法題來看看如何理解遞歸，這是我的一些理解，歡迎大家提出更好的方法。

2.1）漢諾塔問題

漢諾塔問題是個常見問題，就是說有n個大小不等的盤子放在一個塔A上面，自底向上按照從小到大的順序排列。要求將所有n個盤子搬到另一個塔C上面，可以借助一個塔B中轉(zhuǎn)，但是要滿足任何時刻大盤子不能放在小盤子上面。

基本思想分三步，先把上面的N-1個盤子經(jīng)C移到B，然后將最底下的盤子移到C，再講B上面的N-1個盤子經(jīng)A移動到C?？偟臅r間復(fù)雜度f(n)=2f(n-1)+1，所以f(n)=2^n-1。

void hano(char a, char b, char c, int n) {
    if (n > 0) {
        hano(a, c, b, n-1);
        move(a, c);
        hano(b, a, c, n-1);
    }
}

void move(char a, char b)
{
    cout << a << "->" << b << endl;
}

2.2）求二叉樹的深度

這里的深度指的是二叉樹從根結(jié)點到葉結(jié)點最大的高度，比如只有一個結(jié)點，則深度為1，如果有N層，則高度為N。

int depth(struct node* 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函數(shù)呢？我們可以知道定義該函數(shù)的目的就是求二叉樹深度，也就是說我們要是完成了函數(shù)depth，那么depth(root)就能正確返回以root為根結(jié)點的二叉樹的深度。因此我們的代碼中depth(root->left)返回左子樹的深度，而depth(root->right)返回右子樹的深度。盡管這個時候我們還沒有寫完depth函數(shù)，但是我們相信depth函數(shù)能夠正確完成功能。因此我們得到了lDepth和rDepth，而后通過比較返回較大值加1為二叉樹的深度。如果不好理解，可以想象在depth中調(diào)用的函數(shù)depth(root->left)為另外一個同樣名字完成相同功能的函數(shù)，這樣就好理解了。注意Base Case，這里就是當(dāng)root==NULL時，則深度為0，函數(shù)返回0。

2.3）判斷二叉樹是否平衡

一顆平衡的二叉樹是指其任意結(jié)點的左右子樹深度之差不大于1。判斷一棵二叉樹是否是平衡的，可以使用遞歸算法來實現(xiàn)。

bool is_balanced(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL) //基本情況，為空的話，返回true
        return true;
 
    int left = depth(pRoot->m_pLeft);
    int right = depth(pRoot->m_pRight);
    int diff = left - right; //計算左右子樹深度之差
    if(diff > 1 || diff < -1) //如果深度之差大于1返回false
        return false;
 
    return is_balanced(pRoot->m_pLeft) && is_balanced(pRoot->m_pRight); //遞歸判斷左右子樹，注意是&&，即左右子樹都必須是平衡的這棵二叉樹才是平衡的
}

該函數(shù)的功能定義是二叉樹pRoot是平衡二叉樹，即它所有結(jié)點的左右子樹深度之差不大于1。首先判斷根結(jié)點是否滿足條件，如果不滿足，則直接返回false。如果滿足，則需要判斷左子樹和右子樹是否都是平衡二叉樹，若都是則返回true，否則false。

上面代碼性能不高，會重復(fù)遍歷結(jié)點，一個改進的算法是采用后序遍歷的方式遍歷樹的結(jié)點，在遍歷到本結(jié)點前我們已經(jīng)遍歷完了它的左右子樹，我們只需要在遍歷的時候記錄結(jié)點的深度，就可以一邊遍歷一邊判斷該結(jié)點是否是平衡的。代碼如下：

bool is_balanced_2(BinaryTreeNode* pRoot, int* pDepth)
{
    if(pRoot == NULL)
    {
        *pDepth = 0;
        return true;
    }
 
    int left, right;
    if(is_balanced_2(pRoot->m_pLeft, &left) //左子樹平衡
        && is_balanced_2(pRoot->m_pRight, &right)) //右子樹平衡
    {
        int diff = left - right;
        if(diff <= 1 && diff >= -1)
        {
            *pDepth = 1 + (left > right ? left : right);
            return true;
        }
    }
 
    return false;
}

該函數(shù)功能定義是返回以pRoot為根的二叉樹是否是平衡二叉樹，同時把樹的深度保存在pDepth指向的值中?；厩闆r是樹為NULL，則深度為0，返回true。否則只有左右子樹都是平衡的情況下，深度分別存在變量left和right中，判斷左右子樹的深度之差是否不大于1，如果是則返回true，注意還要設(shè)置樹的深度值。

調(diào)用的函數(shù)定義如下：

bool IsBalanced(BinaryTreeNode* pRoot)
{
    int depth = 0;
    return is_balanced_2(pRoot, &depth);
}

2.4）排列算法

排列算法也是遞歸的典范，記得當(dāng)初第一次看時一層層跟代碼，頭都大了，現(xiàn)在從函數(shù)功能上來看確實好理解多了。先看代碼：

void perm(int a[], int k, int N) { //k為起始位置，N為數(shù)組大小
    if (k == N-1) { 
        output(a, N); //輸出排列
    } else {
        for (int i=k; i<N; i++) {
            swap(a, i, k); //交換
            perm(a, k+1, N); //下一次排列
            swap(a, i, k); //恢復(fù)原來的序列
        }
    }
}

首先明確的是perm(a, k, N)函數(shù)的功能:輸出數(shù)組a從位置k開始的所有排列，數(shù)組長度為N。這樣我們在調(diào)用程序的時候，調(diào)用格式為perm(a, 0, N)，即輸出數(shù)組從位置0開始的所有排列，也就是該數(shù)組的所有排列?；A(chǔ)條件是k==N-1，此時已經(jīng)到達最后一個元素，一次排列已經(jīng)完成，直接輸出。否則，從位置k開始的每個元素都與位置k的值交換(包括自己與自己交換)，然后進行下一次排列，排列完成后記得恢復(fù)原來的序列。

假定數(shù)組a大小N=3，則程序調(diào)用perm(a, 0, 3)可以如下理解：
第一次交換0，0，并執(zhí)行perm(a, 1, 3)，執(zhí)行完再次交換0，0，數(shù)組此時又恢復(fù)成初始值。
第二次交換1，0（注意數(shù)組此時是初始值），并執(zhí)行perm(a, 1, 3), 執(zhí)行完再次交換1，0，數(shù)組此時又恢復(fù)成初始值。
第三次交換2，0，并執(zhí)行perm(a, 1, 3)，執(zhí)行完成后交換2，0，數(shù)組恢復(fù)成初始值。

也就是說，從功能上看，首先確定第0個位置，然后調(diào)用perm(a, 1, 3)輸出從1開始的排列，這樣就可以輸出所有排列。而第0個位置可能的值為a[0], a[1],a[2]，這通過交換來保證第0個位置可能出現(xiàn)的值，記得每次交換后要恢復(fù)初始值。

如數(shù)組a={1,2,3}，則程序運行輸出結(jié)果為：1 2 3 ，1 3 2 ，2 1 3 ，2 3 1 ，3 2 1 ，3 1 2 。即先輸出以1為排列第一個值的排列，而后是2和3為第一個值的排列。

2.5）組合算法

組合算法也可以用遞歸實現(xiàn)，只是它的原理跟0-1背包問題類似。即要么選要么不選，注意不能選重復(fù)的數(shù)。完整代碼如下：

#include<iostream>
using namespace std;
#define N 3  //數(shù)組大小為3
int select[N] = {0}; //選擇數(shù)組，用于存儲數(shù)組哪些數(shù)字被選中。
/*輸出數(shù)組中選中的數(shù)*/
void output(int a[], int n)
{
    for (int i=0; i<n; i++) {
        if (select[i])
            cout << a[i] << " ";
    }
    cout << endl;
}
/*數(shù)組a從位置i開始選取k個數(shù)*/
void combination(int a[], int i, int k)
{
    if (i > N) return; //位置超出數(shù)組范圍直接返回，否則非法訪問會出段錯誤
    if (k == 0) {  //選取完了，輸出選取的數(shù)字
        output(a, N);
    } else {
        select[i] = 1;  
        combination(a, i+1, k-1); //第i個數(shù)字被選取，從后續(xù)i+1開始選取k-1個數(shù)
        select[i] = 0;
        combination(a, i+1, k); //第i個數(shù)字不選，則從后續(xù)i+1位置開始還要選取k個數(shù)
    }
}

/*組合主函數(shù)，包括選取1到n個數(shù)字*/
void combination_helper(int a[], int n) {
    for (int k=1; k<=n; k++) {
        combination(a, 0, k);
    }
}

int main()
{
    int a[N] = {1, 2, 3};
    combination_helper(a, N);
    return 0;
}

2.6) 逆序打印字符串

這個比較簡單，代碼如下：

void printReverse(const char *str) {
  if (!*str)
    return;
  printReverse(str + 1);
  putchar(*str);
}

3 多說一句

對遞歸有興趣的，還可以看看這篇文章，用遞歸實現(xiàn)鏈表逆序。

參考資料

• 宋勁松《Linux C編程》遞歸章節(jié)