原文鏈接：http://www.cricode.com/3489.html

題圖：遞歸

在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，遞歸是指在函數(shù)的定義中使用函數(shù)自身的方法。
遞歸算法是一種直接或者間接地調(diào)用自身算法的過(guò)程。在計(jì)算機(jī)編寫程序中，遞歸算法對(duì)解決一大類問(wèn)題是十分有效的，它往往使算法的描述簡(jiǎn)潔而且易于理解。
遞歸算法解決問(wèn)題的特點(diǎn)：
(1) 遞歸就是在過(guò)程或函數(shù)里調(diào)用自身。
(2) 在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。
(3) 遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法解題的運(yùn)行效率較低。所以一般不提倡用遞歸算法設(shè)計(jì)程序。
(4) 在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開(kāi)辟了棧來(lái)存儲(chǔ)。遞歸次數(shù)過(guò)多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計(jì)程序。在實(shí)際編程中尤其要注意棧溢出問(wèn)題。

借助遞歸方法，我們可以把一個(gè)相對(duì)復(fù)雜的問(wèn)題轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，遞歸方法只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。但在帶來(lái)便捷的同時(shí)，也會(huì)有一些缺點(diǎn)，也即：通常用遞歸方法的運(yùn)行效率不高。

遞歸算法實(shí)例

1.Fibonacci函數(shù)

講到遞歸，我們最先接觸到的一個(gè)實(shí)例便是斐波那契數(shù)列。
斐波那契數(shù)列指的是這樣一個(gè)數(shù)列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
特別指出：第0項(xiàng)是0，第1項(xiàng)是第一個(gè)1。
這個(gè)數(shù)列從第二項(xiàng)開(kāi)始，每一項(xiàng)都等于前兩項(xiàng)之和。
斐波那契數(shù)列遞歸法實(shí)現(xiàn)：

123456789101112

int Fib(int n){????if(n<1)????{????????return -1;????}????if(n == 1|| n == 2)????{????????return 1;????}????return Fib(n-1)+Fib(n-2);}

?

2.漢諾塔問(wèn)題

漢諾塔示意圖

漢諾塔是根據(jù)一個(gè)傳說(shuō)形成的數(shù)學(xué)問(wèn)題：
有三根桿子A，B，C。A桿上有N個(gè)(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤移至C桿：
每次只能移動(dòng)一個(gè)圓盤；
大盤不能疊在小盤上面。
提示：可將圓盤臨時(shí)置于B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須遵循上述兩條規(guī)則。
問(wèn)：如何移？最少要移動(dòng)多少次？

最早發(fā)明這個(gè)問(wèn)題的人是法國(guó)數(shù)學(xué)家愛(ài)德華·盧卡斯。

傳說(shuō)印度某間寺院有三根柱子，上串64個(gè)金盤。寺院里的僧侶依照一個(gè)古老的預(yù)言，以上述規(guī)則移動(dòng)這些盤子；預(yù)言說(shuō)當(dāng)這些盤子移動(dòng)完畢，世界就會(huì)滅亡。這個(gè)傳說(shuō)叫做梵天寺之塔問(wèn)題(Tower of Brahma puzzle)。但不知道是盧卡斯自創(chuàng)的這個(gè)傳說(shuō)，還是他受他人啟發(fā)。
若傳說(shuō)屬實(shí)，僧侶們需要264 ? 1步才能完成這個(gè)任務(wù)；若他們每秒可完成一個(gè)盤子的移動(dòng)，就需要5849億年才能完成。整個(gè)宇宙現(xiàn)在也不過(guò)137億年。
這個(gè)傳說(shuō)有若干變體：寺院換成修道院、僧侶換成修士等等。寺院的地點(diǎn)眾說(shuō)紛紜，其中一說(shuō)是位于越南的河內(nèi)，所以被命名為“河內(nèi)塔”。另外亦有“金盤是創(chuàng)世時(shí)所造”、“僧侶們每天移動(dòng)一盤”之類的背景設(shè)定。
佛教中確實(shí)有“浮屠”（塔）這種建筑；有些浮屠亦遵守上述規(guī)則而建。“河內(nèi)塔”一名可能是由中南半島在殖民時(shí)期傳入歐洲的。

以下是漢諾塔問(wèn)題的遞歸求解實(shí)現(xiàn)：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

/* * Project???? : hannoi * File????????: main.cpp * Author??????: iCoding * * Date & Time : Sat Oct 06 21:01:55 2012 * */ usingnamespacestd; #include <iostream> #include <cstdio> voidhannoi(intn,charfrom,charbuffer,charto) { ????if(n==1) ????{ ????????cout<<"Move disk "<<n<<" from "<<from<<" to "<<to<<endl; ????} ????else ????{ ????????hannoi(n-1,from,to,buffer); ????????cout<<"Move disk "<<n<<" from "<<from<<" to "<<to<<endl; ????????hannoi(n-1,buffer,from,to); ????} } intmain() { ????intn; ????cin>>n; ????hannoi(n,'A','B','C'); ????return0; }

更詳細(xì)解析請(qǐng)參考：編程解決漢諾塔問(wèn)題

3.二叉樹遍歷

在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。

一顆簡(jiǎn)單的二叉樹

二叉樹的遍歷分為三種：前(先)序、中序、后序遍歷。

設(shè)L、D、R分別表示二叉樹的左子樹、根結(jié)點(diǎn)和遍歷右子樹，則先(根)序遍歷二叉樹的順序是DLR，中(根)序遍歷二叉樹的順序是LDR，后(根)序遍歷二叉樹的順序是LRD。還有按層遍歷二叉樹。這些方法的時(shí)間復(fù)雜度都是O(n)，n為結(jié)點(diǎn)個(gè)數(shù)。

假設(shè)我們有一個(gè)包含值的value和指向兩個(gè)子結(jié)點(diǎn)的left和right的樹結(jié)點(diǎn)結(jié)構(gòu)。我們可以寫出這樣的過(guò)程：

先序遍歷(遞歸實(shí)現(xiàn))：

1234	visit(node)????print node.value????if node.left??!= null then visit(node.left)????if node.right != null then visit(node.right)

?中序遍歷(遞歸實(shí)現(xiàn))：

1 2 3 4

visit(node) ????ifnode.left??!=nullthenvisit(node.left) ????printnode.value ????ifnode.right!=nullthenvisit(node.right)

?后序遍歷(遞歸實(shí)現(xiàn))：

1234	visit(node)????if node.left??!= null then visit(node.left)????if node.right != null then visit(node.right)????print node.value

4.字符串全排列

問(wèn)題：

寫一個(gè)函數(shù)返回一個(gè)串的所有排列。

解析：

對(duì)于一個(gè)長(zhǎng)度為n的串，它的全排列共有A(n, n)=n!種。這個(gè)問(wèn)題也是一個(gè)遞歸的問(wèn)題， 不過(guò)我們可以用不同的思路去理解它。為了方便講解，假設(shè)我們要考察的串是”abc”， 遞歸函數(shù)名叫permu。

思路一：

我們可以把串“abc”中的第0個(gè)字符a取出來(lái)，然后遞歸調(diào)用permu計(jì)算剩余的串“bc” 的排列，得到{bc, cb}。然后再將字符a插入這兩個(gè)串中的任何一個(gè)空位(插空法)， 得到最終所有的排列。比如，a插入串bc的所有(3個(gè))空位，得到{abc,bac,bca}。 遞歸的終止條件是什么呢？當(dāng)一個(gè)串為空，就無(wú)法再取出其中的第0個(gè)字符了， 所以此時(shí)返回一個(gè)空的排列。代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

typedefvector<string>vs; vspermu(strings){ ????vsresult; ????if(s==""){ ????????result.push_back(""); ????????returnresult; ????} ????stringc=s.substr(0,1); ????vsres=permu(s.substr(1)); ????for(inti=0;i<res.size();++i){ ????????stringt=res[i]; ????????for(intj=0;j<=t.length();++j){ ????????????stringu=t; ????????????u.insert(j,c); ????????????result.push_back(u); ????????} ????} ????returnresult;//調(diào)用result的拷貝構(gòu)造函數(shù)，返回它的一份copy，然后這個(gè)局部變量銷毀(與基本類型一樣) }

?

思路二：

我們還可以用另一種思路來(lái)遞歸解這個(gè)問(wèn)題。還是針對(duì)串“abc”， 我依次取出這個(gè)串中的每個(gè)字符，然后調(diào)用permu去計(jì)算剩余串的排列。 然后只需要把取出的字符加到剩余串排列的每個(gè)字符前即可。對(duì)于這個(gè)例子， 程序先取出a，然后計(jì)算剩余串的排列得到{bc,cb}，然后把a(bǔ)加到它們的前面，得到 {abc,acb}；接著取出b，計(jì)算剩余串的排列得到{ac,ca}，然后把b加到它們前面， 得到{bac,bca}；后面的同理。最后就可以得到“abc”的全序列。代碼如下：

12345678910111213141516

vs permu1(string s){????vs result;????if(s == ""){????????result.push_back("");????????return result;????}????for(int i=0; i<s.length(); ++i){????????string c = s.substr(i, 1);????????string t = s;????????vs res = permu1(t.erase(i, 1));????????for(int j=0; j<res.size(); ++j){????????????result.push_back(c + res[j]);????????}????}????return result;}

更詳細(xì)講解請(qǐng)參考：寫一個(gè)函數(shù)返回一個(gè)串的所有排列

5.八皇后問(wèn)題

問(wèn)題：

經(jīng)典的八皇后問(wèn)題，即在一個(gè)8*8的棋盤上放8個(gè)皇后，使得這8個(gè)皇后無(wú)法互相攻擊( 任意2個(gè)皇后不能處于同一行，同一列或是對(duì)角線上)，輸出所有可能的擺放情況。

解析：

8皇后是個(gè)經(jīng)典的問(wèn)題，如果使用暴力法，每個(gè)格子都去考慮放皇后與否，一共有264?種可能。所以暴力法并不是個(gè)好辦法。由于皇后們是不能放在同一行的， 所以我們可以去掉“行”這個(gè)因素，即我第1次考慮把皇后放在第1行的某個(gè)位置， 第2次放的時(shí)候就不用去放在第一行了，因?yàn)檫@樣放皇后間是可以互相攻擊的。 第2次我就考慮把皇后放在第2行的某個(gè)位置，第3次我考慮把皇后放在第3行的某個(gè)位置， 這樣依次去遞歸。每計(jì)算1行，遞歸一次，每次遞歸里面考慮8列， 即對(duì)每一行皇后有8個(gè)可能的位置可以放。找到一個(gè)與前面行的皇后都不會(huì)互相攻擊的位置， 然后再遞歸進(jìn)入下一行。找到一組可行解即可輸出，然后程序回溯去找下一組可靠解。

我們用一個(gè)一維數(shù)組來(lái)表示相應(yīng)行對(duì)應(yīng)的列，比如c[i]=j表示， 第i行的皇后放在第j列。如果當(dāng)前行是r，皇后放在哪一列呢？c[r]列。 一共有8列，所以我們要讓c[r]依次取第0列，第1列，第2列……一直到第7列， 每取一次我們就去考慮，皇后放的位置會(huì)不會(huì)和前面已經(jīng)放了的皇后有沖突。 怎樣是有沖突呢？同行，同列，對(duì)角線。由于已經(jīng)不會(huì)同行了，所以不用考慮這一點(diǎn)。 同列：c[r]==c[j]; 同對(duì)角線有兩種可能，即主對(duì)角線方向和副對(duì)角線方向。 主對(duì)角線方向滿足，行之差等于列之差：r-j==c[r]-c[j]; 副對(duì)角線方向滿足， 行之差等于列之差的相反數(shù)：r-j==c[j]-c[r]。 只有滿足了當(dāng)前皇后和前面所有的皇后都不會(huì)互相攻擊的時(shí)候，才能進(jìn)入下一級(jí)遞歸。

代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <iostream> usingnamespacestd; intc[20],n=8,cnt=0; voidprint(){ ????for(inti=0;i<n;++i){ ????????for(intj=0;j<n;++j){ ????????????if(j==c[i])cout<<"1 "; ????????????elsecout<<"0 "; ????????} ????????cout<<endl; ????} ????cout<<endl; } voidsearch(intr){ ????if(r==n){ ????????print(); ????????++cnt; ????????return; ????} ????for(inti=0;i<n;++i){ ????????c[r]=i; ????????intok=1; ????????for(intj=0;j<r;++j) ????????????if(c[r]==c[j]||r-j==c[r]-c[j]||r-j==c[j]-c[r]){ ????????????????ok=0; ????????????????break; ????????????} ????????if(ok)search(r+1); ????} } intmain(){ ????search(0); ????cout<<cnt<<endl; ????return0; }

總結(jié)

以上是生活随笔為你收集整理的递归算法实例讲解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。