之前分享了一篇隨機(jī)算法，這次再把以前寫的遞歸算法的文章梳理一下，這篇文章主要是受到宋勁松老師寫的《Linux C編程》的遞歸章節(jié)啟發(fā)寫的屑柔。最能體現(xiàn)算法精髓的非遞歸莫屬了沉帮，希望這篇文章對(duì)初學(xué)遞歸或者對(duì)遞歸不甚了解的筒子們能有所幫助锈死，也懇請(qǐng)各路大牛指正。
1 遞歸算法初探
本段內(nèi)容大部分摘自《linux C一站式編程》穆壕，作者是宋勁松老師待牵，我認(rèn)為這是目前看到的國(guó)內(nèi)關(guān)于linux C編程的最好的一本技術(shù)書籍，強(qiáng)烈推薦喇勋！
關(guān)于遞歸的一個(gè)簡(jiǎ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這個(gè)函數(shù)就是一個(gè)遞歸函數(shù)贰拿，它調(diào)用了它自己。自己直接或間接調(diào)用自己的函數(shù)稱為遞歸函數(shù)渗常。如果覺得迷惑壮不，可以把factorial(n-1)這一步看成是在調(diào)用另一個(gè)函數(shù)－－另一個(gè)有著相同函數(shù)名和相同代碼的函數(shù)，調(diào)用它就是跳到它的代碼里執(zhí)行皱碘，然后再返回factorial(n-1)這個(gè)調(diào)用的下一步繼續(xù)執(zhí)行询一。
為了證明遞歸算法的正確性，我們可以一步步跟進(jìn)去看執(zhí)行結(jié)果。記得剛學(xué)遞歸算法的時(shí)候健蕊，老是有丈二和尚摸不著頭腦的感覺菱阵，那時(shí)候總是想著把遞歸一步步跟進(jìn)去看執(zhí)行結(jié)果。遞歸層次少還算好辦缩功，但是層次一多晴及，頭就大了，完全不知道自己跟到了遞歸的哪一層嫡锌。比如求階乘虑稼，如果只是factorial(3)跟進(jìn)去問題還不大，但是若是factorial(100)要跟進(jìn)去那真的會(huì)煩死人势木。
事實(shí)上蛛倦，我們并不是每個(gè)函數(shù)都需要跟進(jìn)去看執(zhí)行結(jié)果的，比如我們?cè)谧约旱暮瘮?shù)中調(diào)用printf函數(shù)時(shí)啦桌，并沒有鉆進(jìn)去看它是怎么打印的溯壶，因?yàn)槲覀兿嘈潘芡瓿纱蛴」ぷ鳌?/strong>我們?cè)趯慺actorial函數(shù)時(shí)有如下代碼：
...
int recurse = factorial(n-1);
int result = n * recurse;
...
這時(shí)，如果我們相信factorial是正確的甫男，那么傳遞參數(shù)為n-1它就會(huì)返回(n-1)!且改，那么result=n*(n-1)!=n!，從而這就是factorial(n)的結(jié)果板驳。
當(dāng)然這有點(diǎn)奇怪：我們還沒寫完factorial這個(gè)函數(shù)又跛，憑什么要相信factorial(n-1)是正確的？如果你相信你正在寫的遞歸函數(shù)是正確的笋庄，并調(diào)用它效扫，然后在此基礎(chǔ)上寫完這個(gè)遞歸函數(shù)，那么它就會(huì)是正確的直砂，從而值得你相信它正確菌仁。
這么說還是有點(diǎn)玄乎，我們從數(shù)學(xué)上嚴(yán)格證明一下factorial函數(shù)的正確性静暂。剛才說了济丘，factorial(n)的正確性依賴于factorial(n-1)的正確性，只要后者正確洽蛀，在后者的結(jié)果上乘個(gè)n返回這一步顯然也沒有疑問摹迷，那么我們的函數(shù)實(shí)現(xiàn)就是正確的。因此要證明factorial(n)的正確性就是要證明factorial(n-1)的正確性郊供，同理峡碉，要證明factorial(n-1)的正確性就是要證明factorial(n-2)的正確性，依此類推下去驮审，最后是：要證明factorial(1)的正確性就是要證明factorial(0)的正確性鲫寄。而factorial(0)的正確性不依賴于別的函數(shù)調(diào)用吉执，它就是程序中的一個(gè)小的分支return 1;這個(gè)1是我們根據(jù)階乘的定義寫的，肯定是正確的地来，因此factorial(1)的實(shí)現(xiàn)是正確的戳玫，因此factorial(2)也正確，依此類推未斑，最后factorial(n)也是正確的咕宿。
其實(shí)這就是在中學(xué)時(shí)學(xué)的數(shù)學(xué)歸納法，用數(shù)學(xué)歸納法來證明只需要證明兩點(diǎn)：Base Case正確蜡秽，遞推關(guān)系正確府阀。寫遞歸函數(shù)時(shí)一定要記得寫B(tài)ase Case，否則即使遞推關(guān)系正確芽突，整個(gè)函數(shù)也不正確肌似。如果factorial函數(shù)漏掉了Base Case，那么會(huì)導(dǎo)致無限循環(huán)诉瓦。
2 遞歸經(jīng)典問題
從上一節(jié)的一個(gè)關(guān)于求階乘的簡(jiǎn)單例子的論述，我們可以了解到遞歸算法的精髓：要從功能上理解函數(shù)力细，同時(shí)你要相信你正在寫的函數(shù)是正確的睬澡，在此基礎(chǔ)上調(diào)用它，那么它就是正確的眠蚂。下面就從幾個(gè)常見的算法題來看看如何理解遞歸煞聪，這是我的一些理解，歡迎大家提出更好的方法逝慧。
2.1）漢諾塔問題
漢諾塔問題是個(gè)常見問題昔脯，就是說有n個(gè)大小不等的盤子放在一個(gè)塔A上面，自底向上按照從小到大的順序排列笛臣。要求將所有n個(gè)盤子搬到另一個(gè)塔C上面云稚，可以借助一個(gè)塔B中轉(zhuǎn)，但是要滿足任何時(shí)刻大盤子不能放在小盤子上面沈堡。
基本思想分三步静陈，先把上面的N-1個(gè)盤子經(jīng)C移到B，然后將最底下的盤子移到C诞丽，再講B上面的N-1個(gè)盤子經(jīng)A移動(dòng)到C鲸拥。總的時(shí)間復(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é)點(diǎn)到葉結(jié)點(diǎn)最大的高度，比如只有一個(gè)結(jié)點(diǎn)懂衩，則深度為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é)點(diǎn)的二叉樹的深度劣领。因此我們的代碼中depth(root->left)返回左子樹的深度姐军，而depth(root->right)返回右子樹的深度。盡管這個(gè)時(shí)候我們還沒有寫完depth函數(shù)尖淘，但是我們相信depth函數(shù)能夠正確完成功能奕锌。因此我們得到了lDepth和rDepth，而后通過比較返回較大值加1為二叉樹的深度村生。如果不好理解惊暴，可以想象在depth中調(diào)用的函數(shù)depth(root->left)為另外一個(gè)同樣名字完成相同功能的函數(shù)，這樣就好理解了趁桃。注意Base Case辽话，這里就是當(dāng)root==NULL時(shí)，則深度為0卫病，函數(shù)返回0油啤。
2.3）判斷二叉樹是否平衡
一顆平衡的二叉樹是指其任意結(jié)點(diǎn)的左右子樹深度之差不大于1。判斷一棵二叉樹是否是平衡的蟀苛，可以使用遞歸算法來實(shí)現(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; //計(jì)算左右子樹深度之差
if(diff > 1 || diff < -1) //如果深度之差大于1返回false
return false;
return is_balanced(pRoot->m_pLeft) && is_balanced(pRoot->m_pRight); //遞歸判斷左右子樹幽告，注意是&&，即左右子樹都必須是平衡的這棵二叉樹才是平衡的
}
該函數(shù)的功能定義是二叉樹pRoot是平衡二叉樹裆甩，即它所有結(jié)點(diǎn)的左右子樹深度之差不大于1冗锁。首先判斷根結(jié)點(diǎn)是否滿足條件，如果不滿足嗤栓，則直接返回false蒿讥。如果滿足，則需要判斷左子樹和右子樹是否都是平衡二叉樹抛腕，若都是則返回true芋绸，否則false。
上面代碼性能不高担敌，會(huì)重復(fù)遍歷結(jié)點(diǎn)摔敛，一個(gè)改進(jìn)的算法是采用后序遍歷的方式遍歷樹的結(jié)點(diǎn)，在遍歷到本結(jié)點(diǎn)前我們已經(jīng)遍歷完了它的左右子樹全封，我們只需要在遍歷的時(shí)候記錄結(jié)點(diǎn)的深度马昙，就可以一邊遍歷一邊判斷該結(jié)點(diǎn)是否是平衡的桃犬。代碼如下：
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為根的二叉樹是否是平衡二叉樹，同時(shí)把樹的深度保存在pDepth指向的值中行楞≡芟荆基本情況是樹為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)初第一次看時(shí)一層層跟代碼，頭都大了送讲，現(xiàn)在從函數(shù)功能上來看確實(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ù)組長(zhǎng)度為N揭保。這樣我們?cè)谡{(diào)用程序的時(shí)候，調(diào)用格式為perm(a, 0, N)魄宏，即輸出數(shù)組從位置0開始的所有排列，也就是該數(shù)組的所有排列存筏〕杌ィ基礎(chǔ)條件是k==N-1，此時(shí)已經(jīng)到達(dá)最后一個(gè)元素椭坚，一次排列已經(jīng)完成予跌，直接輸出。否則善茎，從位置k開始的每個(gè)元素都與位置k的值交換(包括自己與自己交換)券册，然后進(jìn)行下一次排列，排列完成后記得恢復(fù)原來的序列垂涯。
假定數(shù)組a大小N=3烁焙，則程序調(diào)用perm(a, 0, 3)可以如下理解：
第一次交換0，0耕赘，并執(zhí)行perm(a, 1, 3)骄蝇，執(zhí)行完再次交換0，0操骡，數(shù)組此時(shí)又恢復(fù)成初始值九火。
第二次交換1赚窃，0（注意數(shù)組此時(shí)是初始值），并執(zhí)行perm(a, 1, 3), 執(zhí)行完再次交換1岔激，0勒极，數(shù)組此時(shí)又恢復(fù)成初始值。
第三次交換2虑鼎，0辱匿，并執(zhí)行perm(a, 1, 3)，執(zhí)行完成后交換2震叙，0掀鹅，數(shù)組恢復(fù)成初始值。
也就是說媒楼，從功能上看乐尊，首先確定第0個(gè)位置，然后調(diào)用perm(a, 1, 3)輸出從1開始的排列划址，這樣就可以輸出所有排列扔嵌。而第0個(gè)位置可能的值為a[0], a[1],a[2]，這通過交換來保證第0個(gè)位置可能出現(xiàn)的值夺颤，記得每次交換后要恢復(fù)初始值痢缎。
如數(shù)組a={1,2,3}，則程序運(yùn)行輸出結(jié)果為：1 2 3 世澜，1 3 2 独旷，2 1 3 ，2 3 1 寥裂，3 2 1 嵌洼，3 1 2 。即先輸出以1為排列第一個(gè)值的排列封恰，而后是2和3為第一個(gè)值的排列麻养。
2.5）組合算法
組合算法也可以用遞歸實(shí)現(xiàn)，只是它的原理跟0-1背包問題類似诺舔。即要么選要么不選鳖昌，注意不能選重復(fù)的數(shù)。完整代碼如下：
#include<iostream>
using namespace std;
#define N 3 //數(shù)組大小為3
int select[N] = {0}; //選擇數(shù)組低飒，用于存儲(chǔ)數(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個(gè)數(shù)*/
void combination(int a[], int i, int k)
{
if (i > N) return; //位置超出數(shù)組范圍直接返回，否則非法訪問會(huì)出段錯(cuò)誤
if (k == 0) { //選取完了褥赊，輸出選取的數(shù)字
output(a, N);
} else {
select[i] = 1;
combination(a, i+1, k-1); //第i個(gè)數(shù)字被選取车要，從后續(xù)i+1開始選取k-1個(gè)數(shù)
select[i] = 0;
combination(a, i+1, k); //第i個(gè)數(shù)字不選，則從后續(xù)i+1位置開始還要選取k個(gè)數(shù)
}
}
/*組合主函數(shù)崭倘，包括選取1到n個(gè)數(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) 逆序打印字符串
這個(gè)比較簡(jiǎn)單翼岁，代碼如下：
void printReverse(const char *str) {
if (!*str)
return;
printReverse(str + 1);
putchar(*str);
}
3 多說一句
對(duì)遞歸有興趣的类垫，還可以看看這篇文章，用遞歸實(shí)現(xiàn)鏈表逆序琅坡。
參考資料
- 宋勁松《Linux C編程》遞歸章節(jié)
