5.5　遞歸

遞歸就是在程序開(kāi)發(fā)過(guò)程中，函數(shù)調(diào)用自己的一種編程思路。使用遞歸編寫代碼可以大量減少程序的代碼量，但是會(huì)提高系統(tǒng)資源的占用率。C++語(yǔ)言也支持遞歸。本節(jié)將詳細(xì)講解遞歸的相關(guān)內(nèi)容。

5.5.1　什么是遞歸

遞歸來(lái)源于英文recursion，可以翻譯為遞推、遞歸。遞歸就是將復(fù)雜的問(wèn)題，按照特定規(guī)律，逐步簡(jiǎn)化的一個(gè)過(guò)程。遞歸由遞推、終止條件、回溯及遞歸方式四部分組成。

? 遞推：將復(fù)雜數(shù)據(jù)進(jìn)行簡(jiǎn)化的過(guò)程。

? 終止條件：遞推過(guò)程的終止界限。

? 回溯：將簡(jiǎn)化的所有數(shù)據(jù)進(jìn)行回推的過(guò)程。

? 遞歸方式：遞推與回溯過(guò)程中都需要遵循的簡(jiǎn)化數(shù)據(jù)和回推數(shù)據(jù)的規(guī)律。

下面以計(jì)算4！（4的階乘）的值為例進(jìn)一步講解遞歸的思路。按照數(shù)學(xué)的解題思路，我們會(huì)將4！轉(zhuǎn)換為一個(gè)等式，然后計(jì)算4！的值，如下所示。

從數(shù)學(xué)解題思路中可以發(fā)現(xiàn)如下規(guī)律。

如果使用變量n來(lái)代替數(shù)字，則可以轉(zhuǎn)換為：

所以，遞歸方式應(yīng)該為n！=n*（n-1）！。而數(shù)據(jù)遞歸的終止條件是n=1。找到了遞歸方式與終止條件，下面對(duì)4！進(jìn)行遞歸處理。

首先，對(duì)數(shù)據(jù)進(jìn)行遞推簡(jiǎn)化處理。

? 第1次遞推，將4！拆分為4*3！。此時(shí)4為最簡(jiǎn)單數(shù)據(jù)，3！為復(fù)雜數(shù)據(jù)。

? 第2次遞推，將3！拆分為3*2！，此時(shí)3為簡(jiǎn)單數(shù)據(jù)，2！為復(fù)雜數(shù)據(jù)。

? 第3次遞推，將2！拆分為2*1！，此時(shí)2為簡(jiǎn)單數(shù)據(jù)，1！為復(fù)雜數(shù)據(jù)。

? 第4次遞推，將1！拆分為1*1，1為最簡(jiǎn)單數(shù)據(jù)，符合終止遞推過(guò)程的條件。

然后，開(kāi)始回溯處理。

? 運(yùn)算結(jié)果為1*1=1，將1向上第1次回溯。

? 替換后為2*1=2，將2向上第2次回溯。

? 替換后為3*2=6，將6向上第3次回溯。

? 替換后為4*6=24，此時(shí)，遞歸完成，計(jì)算出4！的值為24。

整個(gè)過(guò)程就是遞歸。為了更好地理解，我們用圖5.8展示遞歸的過(guò)程。

5.5.2　遞歸的實(shí)現(xiàn)

C++語(yǔ)言使用遞歸是通過(guò)函數(shù)反復(fù)調(diào)用自身來(lái)實(shí)現(xiàn)的，這樣做會(huì)大量節(jié)省代碼，但是會(huì)增加運(yùn)算量。其語(yǔ)法形式如下。

其中，遞歸方式由調(diào)用自身的函數(shù)為基礎(chǔ)組成，遞推從調(diào)用自身的函數(shù)開(kāi)始，回溯從終止條件的return語(yǔ)句開(kāi)始。

【示例5-8】下面演示計(jì)算10的階乘的值。

程序運(yùn)行結(jié)果如下。

計(jì)算10的階乘的遞歸過(guò)程如圖5.9所示。

遞歸過(guò)程簡(jiǎn)單說(shuō)就是一種化繁為簡(jiǎn)的過(guò)程，在編程語(yǔ)言中十分常見(jiàn)。一般而言，遞歸函數(shù)過(guò)程對(duì)于計(jì)算階乘、級(jí)數(shù)、指數(shù)運(yùn)算有特殊效果。