什么叫遞歸？（先定義一個(gè)比較簡(jiǎn)單的說(shuō)法，為了理解，不一定對(duì)）
遞歸：無(wú)限調(diào)用自身這個(gè)函數(shù)，每次調(diào)用總會(huì)改動(dòng)一個(gè)關(guān)鍵變量，直到這個(gè)關(guān)鍵變量達(dá)到邊界的時(shí)候，不再調(diào)用。
比如說(shuō)我要你先求一個(gè)N!的結(jié)果
你說(shuō)我會(huì)用循環(huán)啊（沒(méi)錯(cuò)，但是現(xiàn)在是學(xué)遞歸）
int factorial(int x,int ans){ if(x==1) return ans; factorial(x-1,ans*x);}怎么樣，對(duì)于C基礎(chǔ)如果掌握的還行的話(huà)，這段代碼應(yīng)該很好理解。遞歸，顧名思義就是“遞”和“歸”。也就是說(shuō)，寫(xiě)每一個(gè)遞歸函數(shù)的時(shí)候，都應(yīng)該在寫(xiě)之前考慮清楚，哪里體現(xiàn)了“遞”，哪里體現(xiàn)了“歸”。
但是常常遞歸函數(shù)會(huì)比較復(fù)雜， “遞”和“歸”看起來(lái)并不是那么明顯，這就需要我們進(jìn)一步來(lái)理解遞歸算法的思想。
比如說(shuō)我現(xiàn)在要你用輾轉(zhuǎn)相除法求出兩個(gè)數(shù)的最大公約數(shù)，遞歸函數(shù)如下：
int gcd(int a,int b){ return a%b==0?b:gcd(b,a%b);}這是一段很常用的代碼，我們知道，在學(xué)習(xí)過(guò)程中不求甚解是最不應(yīng)該的。因此現(xiàn)在來(lái)仔細(xì)看一看。這里的“遞”和“歸”放在同一行。首先進(jìn)行判斷a==b?（我們可以想象成“歸”的內(nèi)容，如果這個(gè)條件符合的話(huà)）。當(dāng)然，如果不符合這個(gè)判斷，那就繼續(xù)“遞”，也就是繼續(xù)進(jìn)行gcd(b,a%b);
看到這里，你就會(huì)發(fā)現(xiàn)，遞歸不就是循環(huán)的另一種方式么？
說(shuō)對(duì)了一半，不過(guò)遞歸是一種思想，現(xiàn)在還暫時(shí)不能說(shuō)透，需要大家先比較一下循環(huán)和遞歸的相同點(diǎn)和不同點(diǎn)（飯一口一口吃，別著急）
總結(jié)循環(huán)和遞歸：
相同點(diǎn)： （1）都是通過(guò)控制一個(gè)變量的邊界（或者多個(gè)），來(lái)改變多個(gè)變量為了得到所需要的值，而反復(fù)而執(zhí)行的； （2）都是按照預(yù)先設(shè)計(jì)好的推斷實(shí)現(xiàn)某一個(gè)值求取；（請(qǐng)注意，在這里循環(huán)要更注重過(guò)程，而遞歸偏結(jié)果一點(diǎn)）
不同點(diǎn)： （1）遞歸通常是逆向思維居多，“遞”和“歸”不一定容易發(fā)現(xiàn)（比較難以理解）；而循環(huán)從開(kāi)始條件到結(jié)束條件，包括中間循環(huán)變量，都需要表達(dá)出來(lái)（比較簡(jiǎn)潔明了）。
簡(jiǎn)單的來(lái)說(shuō)就是：用循環(huán)能實(shí)現(xiàn)的，遞歸一般可以實(shí)現(xiàn)，但是能用遞歸實(shí)現(xiàn)的，循環(huán)不一定能。因?yàn)橛行╊}目①只注重循環(huán)的結(jié)束條件和循環(huán)過(guò)程，而往往這個(gè)結(jié)束條件不易表達(dá)（也就是說(shuō)用循環(huán)并不好寫(xiě)）；②只注重循環(huán)的次數(shù)而不注重循環(huán)的開(kāi)始條件和結(jié)束條件（這個(gè)循環(huán)更加無(wú)從下手了）。
來(lái)看看“漢諾塔問(wèn)題”
如圖，漢諾塔問(wèn)題是指有三根桿子A,B,C。C桿上有若干碟子，把所有碟子從A桿上移到C桿上，每次只能移動(dòng)一個(gè)碟子，大的碟子不能疊在小的碟子上面。求最少要移動(dòng)多少次？
這是一個(gè)循環(huán)只注重循環(huán)次數(shù)的常見(jiàn)例子，我們知道，用循環(huán)有點(diǎn)無(wú)從下手（就目前作者水平來(lái)看），但是遞歸就很好寫(xiě)了。
漢諾塔，什么鬼，我不會(huì)啊？
別急，慢慢來(lái)。
我們首先需要一點(diǎn)思維：解決n塊盤(pán)子從A移動(dòng)到C，那么我只需要先把n-1塊盤(pán)子從A移到B，然后把最下面的第n塊盤(pán)子從A移到C，最后把n-1塊盤(pán)子從B移到C（這就完成了）。
等等，那么如何把n-1塊盤(pán)子從A移到B？
很好，這說(shuō)明你已經(jīng)開(kāi)始遞歸入門(mén)了。
同樣這樣去想：解決n-1塊盤(pán)子從A移動(dòng)到B，那么我只需要先把n-2塊盤(pán)子從A移動(dòng)到C，然后把倒數(shù)第二塊盤(pán)子從A移到B，最后把n-2塊盤(pán)子從C移到B（這就完成了）。
這就是遞歸的“遞”！
那么“歸”呢？n==1的時(shí)候？
Bingo
int i; //記錄步數(shù) //i表示進(jìn)行到的步數(shù),將編號(hào)為n的盤(pán)子由from柱移動(dòng)到to柱(目標(biāo)柱) void move(int n,char from,char to){ 實(shí)際上這里面已經(jīng)使用到了一點(diǎn)點(diǎn)棧的思想（即最上面的最先考慮變化），但其實(shí)遞歸有的時(shí)候就是真的可以理解為棧！到了這一步，相信大家應(yīng)該已經(jīng)有所明白。循環(huán)其實(shí)就是一個(gè)控制變量從開(kāi)始條件走到結(jié)束條件的過(guò)程（在循環(huán)的過(guò)程順帶把其他變量也改變一下），因此需要控制變量，開(kāi)始條件，結(jié)束條件（缺一不可）。但是遞歸只要告訴你“歸”是什么，如何去“遞”，不管過(guò)程如何，只要計(jì)算結(jié)果即可。
（2）遞歸可以是多個(gè)“遞”，也可以是多個(gè)“歸”；而循環(huán)由始至終都只由一個(gè)變量控制（就算有幾個(gè)變量同時(shí)控制）也只有一個(gè)出口，每次循環(huán)也只是一個(gè)“遞”。
再看一個(gè)例子
用二分思想建立二叉樹(shù)（通常的是遞歸實(shí)現(xiàn)），比如說(shuō)線(xiàn)段樹(shù)
//root 節(jié)點(diǎn)序號(hào) //left 節(jié)點(diǎn)維護(hù)的左邊界 //right 節(jié)點(diǎn)維護(hù)的右邊界void build(int root,int left,int right){ if(left==right) return ; int mid=(left+right)/2; build(root*2，left,mid); build(root*2+1,mid+1,right);}如果你是新手看不太懂也沒(méi)關(guān)系，現(xiàn)在最主要的是明白：在這個(gè)程序里面只有一個(gè)“歸”，但是有兩個(gè)“遞”。
那么如果學(xué)過(guò)一點(diǎn)但是對(duì)這一塊還不明白的怎么辦呢？別急，聽(tīng)我來(lái)解釋?zhuān)?/p>
實(shí)際上，這兩個(gè)“遞”是按照先后分別進(jìn)行的，等到第一個(gè)“遞”執(zhí)行完（也就是到了“歸”的條件之后），才開(kāi)始執(zhí)行第二個(gè)“遞”。也就是說(shuō)，通常在建樹(shù)的時(shí)候，都不是一層一層同時(shí)建的，而是先建一棵子樹(shù)，等到這棵子樹(shù)全部建完之后，才開(kāi)始建立另外一棵子樹(shù)。
那就會(huì)問(wèn)了，一棵子樹(shù)建完了之后root值不會(huì)變么，root值變了之后還怎么建另外一棵子樹(shù)呢？
root值不會(huì)變！大家請(qǐng)注意，這里root*2是寫(xiě)在遞歸函數(shù)里面的，實(shí)際上并沒(méi)有賦值？為什么要這樣寫(xiě)？因?yàn)槿绻贿@樣寫(xiě)，你直接寫(xiě)在外邊的話(huà)，一棵子節(jié)點(diǎn)到達(dá)葉子節(jié)點(diǎn)之后，需要一層一層往上回溯（在這里提到了回溯的思想），而回溯就會(huì)無(wú)故產(chǎn)生很多不必要的時(shí)間復(fù)雜度，降低了遞歸效率（實(shí)際上遞歸的時(shí)間效率本來(lái)就有一點(diǎn)偏低）。
所以到目前為止，我只是介紹一些很常見(jiàn)的簡(jiǎn)單的遞歸，但是在接下來(lái)，我就需要說(shuō)一些比較深層一點(diǎn)的知識(shí)了。
首先要理解一下什么是回溯（寫(xiě)的不好，大佬勿噴）
回溯：在遞歸的過(guò)程中由于改變的量需要倒退到某一個(gè)位置而執(zhí)行的步驟。
先來(lái)看一個(gè)簡(jiǎn)單的素?cái)?shù)環(huán)問(wèn)題：
給出1到n的n個(gè)連續(xù)的正整數(shù)（這里n暫時(shí)等于6），并且把這n個(gè)數(shù)填寫(xiě)在如下圖的n個(gè)圓圈里面（當(dāng)然是不重復(fù)不遺漏了）。要求是每一個(gè)位置上面的數(shù)跟他相鄰的數(shù)之和都為一個(gè)素?cái)?shù)，打印并輸出最后滿(mǎn)足條件的情況。
首先明白，開(kāi)始條件是1，把1填寫(xiě)在第一個(gè)位置，然后在剩下的n-1個(gè)數(shù)字里找到一個(gè)滿(mǎn)足與1的和是一個(gè)素?cái)?shù)的數(shù)（當(dāng)然如果有多個(gè)，先靠前的先考慮）。接下來(lái)再繼續(xù)從剩下n-2個(gè)數(shù)字里找到一個(gè)與這個(gè)數(shù)的和又是一個(gè)素?cái)?shù)的數(shù)（當(dāng)然如果有多個(gè)，同上。）。。。最后的一個(gè)數(shù)只要滿(mǎn)足與最開(kāi)始的數(shù)1之和是一個(gè)素?cái)?shù)的話(huà)，這個(gè)情況就滿(mǎn)足了（就可以打印輸出這樣一個(gè)例子了）
但事情并沒(méi)有想象的那么簡(jiǎn)單。。。（告訴我如果在中途尋找的過(guò)程中從剩下的數(shù)里找不到與當(dāng)前數(shù)的的和是一個(gè)素?cái)?shù)的情況出現(xiàn)怎么辦？在線(xiàn)等）
這就表明這樣一條路終歸是一條思路，你要往回走了！這就很符合我們給回溯的定義了，此時(shí)這個(gè)改變的量需要倒退的前面一步從另外一個(gè)方向?qū)ふ伊恕＃ㄟ€是舉栗子吧）
比如說(shuō)：
1->2->3->4 突然發(fā)現(xiàn)5和6都不滿(mǎn)足要求了
那么就倒退，準(zhǔn)備找另外滿(mǎn)足要求的數(shù)
1->2->3 又發(fā)現(xiàn)除了4以外3跟5或者3跟6也不滿(mǎn)足要求
那就繼續(xù)倒退，繼續(xù)準(zhǔn)備找另外滿(mǎn)足要求的數(shù)
1->2->5->6 接下來(lái)發(fā)現(xiàn)6跟3或者6跟4不滿(mǎn)足要求
…(還想繼續(xù)下去？你是要玩死我？別這樣，我也累啊，看一兩個(gè)就行了，啊！) 最后發(fā)現(xiàn)滿(mǎn)足條件的一個(gè)是
1->4->3->2->5->6
大家應(yīng)該已經(jīng)懂了，上面的倒退，實(shí)際上就是回溯。（暫時(shí)這樣簡(jiǎn)單的理解吧，錯(cuò)了也不能怪你們）
實(shí)際上，遞歸+回溯就已經(jīng)是dfs(深度優(yōu)先搜索)的內(nèi)容范疇了。
void dfs(int x){ if(x==n+1&&prime(a[x-1]+a[1])) //如果滿(mǎn)足條件就可以打印輸出數(shù)據(jù)了，這里就是“歸” { for(int i=1;i<n;i++) cout<<a[i]<<" "; cout<<a[n]<<endl; } else //否則就繼續(xù)“遞” { for(int i=2;i<=n;i++) { if(!vis[i]&&prime(i+a[x-1])) { vis[i]=1; //vis[]是一個(gè)標(biāo)記數(shù)組，表示當(dāng)前的數(shù)字已經(jīng)被使用過(guò)了 a[x]=i; dfs(x+1); //“遞”的入口 vis[i]=0; //請(qǐng)注意，回溯點(diǎn)在這里 } } }}大家可能前面都看懂了，比如說(shuō)“遞”和“歸”，vis[]標(biāo)記數(shù)組什么的。但是最后一個(gè)vis[i]=0是啥意思？難道不多余么？
不多余！前面我已經(jīng)拿建樹(shù)給大家講過(guò)遞歸的“工作原理”，它是先無(wú)限遞歸，然后到達(dá)某個(gè)條件之后，回溯到上面一個(gè)位置，繼續(xù)向其他方向遞歸。而這個(gè)vis[i]=0就是清楚當(dāng)前數(shù)字的標(biāo)記，表示從當(dāng)前節(jié)點(diǎn)開(kāi)始，之后遞歸過(guò)的內(nèi)容統(tǒng)統(tǒng)清空（也就是回溯）。然后根據(jù)循環(huán)，進(jìn)行下面一個(gè)方向的繼續(xù)遞歸。
這也是dfs的經(jīng)典思想所在！
因此，講到這里，不說(shuō)說(shuō)dfs似乎也是吊大家胃口了。所以接下來(lái)，就聊一聊dfs中的遞歸。
比如說(shuō)hdu上面的1312 http://acm.split.hdu.edu.cn/showproblem.php?pid=1312
我簡(jiǎn)單說(shuō)一下意思，如下圖，判斷一個(gè)圖內(nèi)包括@符號(hào)在內(nèi)的所有‘.’和‘@’的個(gè)數(shù)。有個(gè)限制條件，如果‘.’被‘#’封死，則‘.’不可訪問(wèn)。
6 9 （分別表示行和列）
....#......#..............................#@...#.#..#.45
比如說(shuō)這一個(gè)數(shù)據(jù)就有三個(gè)‘.’被邊界和‘#’困死而不可訪問(wèn)，因此只有45個(gè)點(diǎn)滿(mǎn)足要求。
本題的思路就是從’@’點(diǎn)開(kāi)始，bfs搜索每一個(gè)點(diǎn)，分成上下左右四個(gè)方向分別遞歸搜索。
int cnt,a[4]={-1,0,1,0},b[4]={0,1,0,-1},n,m,vis[22][22];char s[22][22]; void dfs(int x,int y){ for(int i=0;i<4;i++) //四個(gè)方向循環(huán)搜索 { int p=x+a[i]; int q=y+b[i]; if(p>=0&&p<m&&q>=0&&q<n&&!vis[p][q]&&s[p][q]=='.') //判斷遞歸條件，包括在數(shù)組邊界之內(nèi)，該點(diǎn)未被標(biāo)記 { vis[p][q]=1; //標(biāo)記該點(diǎn) cnt++; //計(jì)數(shù)變量加一 dfs(p,q); //遞歸搜索 } }}請(qǐng)注意：本題中因?yàn)榭梢蕴崆芭袛嘞乱粋€(gè)要搜索的點(diǎn)是否為‘#’而免于回溯，降低時(shí)間復(fù)雜度。
并且大家可以看出，上面的代碼實(shí)際上是稍微復(fù)雜一點(diǎn)的遞歸算法（把從‘@’出發(fā)的每一個(gè)方向看成一條線(xiàn)段，而這條線(xiàn)段的另外一個(gè)終點(diǎn)就是邊界或者’#’），因此這就是可以看成循環(huán)了四次的遞歸算法，而每一次遞歸調(diào)用的過(guò)程，每一方向又看成從當(dāng)前點(diǎn)出發(fā)的一條線(xiàn)段。如此反復(fù)。（中間的cnt用來(lái)計(jì)數(shù)）
請(qǐng)注意，cnt就是就是遞歸的次數(shù)（因?yàn)闆](méi)有回溯，如果有回溯，計(jì)數(shù)的話(huà)不一定等于遞歸的次數(shù)）
到此，基本知識(shí)點(diǎn)已經(jīng)全部講完，下面給出一點(diǎn)個(gè)人關(guān)于寫(xiě)遞歸算法的建議吧：
（1）把遞歸當(dāng)成復(fù)雜的循環(huán)來(lái)寫(xiě)，如果不明白過(guò)程，多模擬幾遍數(shù)據(jù)；
（2）把遞歸逆向?qū)懙臅r(shí)候當(dāng)做一個(gè)棧來(lái)實(shí)現(xiàn)（即符合先進(jìn)先出的思想）；
（3）當(dāng)遞歸和回溯結(jié)合在一起的時(shí)候需要明白遞歸次數(shù)和統(tǒng)計(jì)次數(shù)之間的練習(xí)和區(qū)別；
（4）但遞歸有多個(gè)“遞”和“歸”的時(shí)候，選擇一個(gè)重點(diǎn)的“遞”和“歸”作為匹配，即時(shí)題目即時(shí)分析，注意隨機(jī)應(yīng)變即可。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
