C語言遞歸

2019-11-17 05:22:58

字體：大中小

供稿：網(wǎng)友

　　C語言函數(shù)可以自我調(diào)用。假如函數(shù)內(nèi)部一個(gè)語句調(diào)用了函數(shù)自己，則稱這個(gè)函數(shù)是“遞歸”。遞歸是以自身定義的過程。也可稱為“循環(huán)定義”。
遞歸的例子很多。例如定義整數(shù)的遞歸方法是用數(shù)字1，2，3，4，5，6，7，8，9加上或減去一個(gè)整數(shù)。例如，數(shù)字15是7+8；數(shù)字21是9+12；數(shù)字12是9+3。
一種可遞歸的計(jì)算機(jī)語言，它的函數(shù)能夠自己調(diào)用自己。一個(gè)簡(jiǎn)單的例子就是計(jì)算整數(shù)階乘的函數(shù)factor()數(shù)N的階乘是1到N之間所有數(shù)字的乘積。例如3的階乘是1×2×3，即是６。
factor()和其等效函數(shù)fact()如例4-10所示。
C語言遞歸

非遞歸函數(shù)fact()的執(zhí)行應(yīng)該是易于理解的。它應(yīng)用一個(gè)從1開始到指定數(shù)值結(jié)束的循環(huán)。
在循環(huán)中，用“變化”的乘積依次去乘每個(gè)數(shù)。
factor()的遞歸執(zhí)行比fact()稍復(fù)雜。當(dāng)用參數(shù)1調(diào)用factor()時(shí)，函數(shù)返回1；除此之外的其它值調(diào)用將返回factor(n-1)*n這個(gè)乘積。為了求出這個(gè)表達(dá)式的值，用（n-1）調(diào)用factor()一直到n等于1，調(diào)用開始返回。
計(jì)算2的階乘時(shí)對(duì)factor()的首次調(diào)用引起了以參數(shù)1對(duì)factor()的第二次調(diào)用。這次調(diào)用返回1，然后被2乘（n的初始值），答案是2（把PRintf()語句插入到factor()中，察看各級(jí)調(diào)用及其中間答案，是很有趣的）。
當(dāng)函數(shù)調(diào)用自己時(shí)，在棧中為新的局部變量和參數(shù)分配內(nèi)存，函數(shù)的代碼用這些變量和參數(shù)重新運(yùn)行。遞歸調(diào)用并不是把函數(shù)代碼重新復(fù)制一遍，僅僅參數(shù)是新的。當(dāng)每次遞歸調(diào)用返回時(shí)，老的局部變量和參數(shù)就從棧中消除，從函數(shù)內(nèi)此次函數(shù)調(diào)用點(diǎn)重新啟動(dòng)運(yùn)行。可遞歸的函數(shù)被說成是對(duì)自身的“推入和拉出”。
大部分遞歸例程沒有明顯地減少代碼規(guī)模和節(jié)省內(nèi)存空間。另外，大部分例程的遞歸形式比非遞歸形式運(yùn)行速度要慢一些。這是因?yàn)楦郊拥暮瘮?shù)調(diào)用增加了時(shí)間開銷（在許多情況下，速度的差別不太明顯）。對(duì)函數(shù)的多次遞歸調(diào)用可能造成堆棧的溢出。不過溢出的可能性不大，因?yàn)楹瘮?shù)的參數(shù)和局部變量是存放在堆棧中的。每次新的調(diào)用就會(huì)產(chǎn)生一些變量的復(fù)制品。這個(gè)堆棧沖掉其它數(shù)據(jù)和程序的存儲(chǔ)區(qū)域的可能性是存在的。但是除非遞歸程序運(yùn)行失控，否則不必為上述情況擔(dān)心。
遞歸函數(shù)的主要優(yōu)點(diǎn)是可以把算法寫的比使用非遞歸函數(shù)時(shí)更清楚更簡(jiǎn)潔，而且某些問題，非凡是與人工智能有關(guān)的問題，更適宜用遞歸方法。遞歸的另一個(gè)優(yōu)點(diǎn)是，遞歸函數(shù)不會(huì)受到懷疑，較非遞歸函數(shù)而言，某些人更相信遞歸函數(shù)。編寫遞歸函數(shù)時(shí)，必須在函數(shù)的某些地方使用if語句，強(qiáng)迫函數(shù)在未執(zhí)行遞歸調(diào)用前返回。假如不這樣做，在調(diào)用函數(shù)后，它永遠(yuǎn)不會(huì)返回。在遞歸函數(shù)中不使用if語句，是一個(gè)很常見的錯(cuò)誤。在開發(fā)過程中廣泛使用printf()和getchar()可以看到執(zhí)行過程，并且可以在發(fā)現(xiàn)錯(cuò)誤后停止運(yùn)行。

上一篇：C語言的預(yù)處理程序與注釋

下一篇：實(shí)現(xiàn)問題