C語言遞歸函數(shù)的執(zhí)行與求解

導(dǎo)語：函數(shù)的遞歸調(diào)用是在調(diào)用一個(gè)函數(shù)的執(zhí)行過程中，直接或間接地調(diào)用該函數(shù)本身，使用遞歸函數(shù)的程序結(jié)構(gòu)清晰，簡(jiǎn)單、易懂。下面就由小編為大家介紹一下C語言遞歸函數(shù)的執(zhí)行與求解，歡迎大家閱讀!

(資料圖片僅供參考)

1 遞歸函數(shù)

C語言的特點(diǎn)之一就在于允許函數(shù)的遞歸調(diào)用，即允許在函數(shù)內(nèi)部直接或間接的調(diào)用函數(shù)自身，被調(diào)用的函數(shù)被稱為遞歸函數(shù)。遞歸調(diào)用有直接遞歸調(diào)用和間接遞歸調(diào)用兩種形式，遞歸函數(shù)常用于解決那些需要分多次求解且每次求解過程都基本類似的問題。構(gòu)造遞歸函數(shù)的關(guān)鍵在于尋找遞歸算法和終結(jié)條件。遞歸算法就是解決問題所采取的方法和步驟，一般只要對(duì)問題的若干次求解過程進(jìn)行分析和歸納，找出每一次求解過程之間的規(guī)律性，就可歸納出遞歸算法，終結(jié)條件是為了終結(jié)函數(shù)的遞歸調(diào)用而設(shè)置的一個(gè)條件或規(guī)則。遞歸調(diào)用的一般形式為：

函數(shù)類型 函數(shù)名(參數(shù)列表)

{

，，，，，

函數(shù)名(參數(shù)列表)

…..

}

2 遞歸條件

使用遞歸調(diào)用編寫程序時(shí)，要注意以下幾點(diǎn)：

(1)可以通過遞歸調(diào)用來縮小問題規(guī)模，且新問題與原問題有著相同的形式，只是所處理的對(duì)象具有一定的規(guī)律性。也就是說解決問題的方法相同，調(diào)用函數(shù)的參數(shù)有規(guī)律的遞增或遞減。

(2)遞歸函數(shù)必須有一個(gè)終止處理?xiàng)l件，即必須有一個(gè)明確的結(jié)束條件，必須在適當(dāng)?shù)臅r(shí)候能夠結(jié)束遞歸調(diào)用，否則會(huì)使程序陷入死循環(huán)，導(dǎo)致系統(tǒng)崩潰。

(3)有些使用遞歸算法求解的問題也可使用普通循環(huán)算法來實(shí)現(xiàn)，相較于循環(huán)程序，遞歸程序結(jié)構(gòu)簡(jiǎn)單，邏輯清晰，但運(yùn)行效率低，故在有其他算法可以代替的情況下，要盡量避免使用遞歸算法編寫程序。

3 遞歸實(shí)例

例：使用遞歸方法求n!。

在數(shù)學(xué)上n!=1×2×3×…×n-1×n，我們可以寫成以下形式

1 當(dāng)n=0或n=1時(shí)

n!=

(n-1)!×n 當(dāng)n>1時(shí)

根據(jù)以上形式，可以寫出如下遞歸調(diào)用程序：

int f(n)

{

if(n==1||n==0)

return 1;

else

return f(n-1)*n;

}

int main()

{

int n;

scanf(“%d”，&n);

if(n<0)

printf(“data error!”);

else

printf(“%d”，f(n));

return 0;

}

4 遞歸函數(shù)執(zhí)行過程

遞歸調(diào)用之所以能夠?qū)崿F(xiàn)，是因?yàn)楹瘮?shù)在每一次執(zhí)行過程中，都會(huì)把自己所有形參變量和局部變量復(fù)制一個(gè)副本，壓入棧中，這些副本分別位于棧中不同的內(nèi)存空間，和函數(shù)的其他執(zhí)行過程毫不相干，這種機(jī)制使得遞歸調(diào)用成為可能。一個(gè)遞歸函數(shù)的執(zhí)行過程類似于調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)的多層嵌套調(diào)用，因此，和遞歸函數(shù)的執(zhí)行過程密切相關(guān)的一個(gè)重要概念就是遞歸函數(shù)運(yùn)行的層次。假設(shè)調(diào)用該遞歸函數(shù)的主函數(shù)為第0層，則從主函數(shù)調(diào)用遞歸函數(shù)則進(jìn)入第一層;從第n層調(diào)用本函數(shù)則進(jìn)入“下一層”，即第n+1層。反之，退出第n層遞歸調(diào)用應(yīng)返回至“上一層”，即第n-1層。

在遞歸函數(shù)的執(zhí)行過程中，另一個(gè)非常重要的概念是“遞歸工作?！钡氖褂茫?dāng)一個(gè)函數(shù)(調(diào)用者)調(diào)用另外一個(gè)函數(shù)(被調(diào)用者)時(shí)，系統(tǒng)會(huì)把調(diào)用者的所有實(shí)在參數(shù)，被調(diào)用者的形式參數(shù)、局部變量，以及調(diào)用者的返回地址等信息全部壓入“遞歸工作?！睍捍妫?dāng)被調(diào)用者執(zhí)行完畢時(shí)，系統(tǒng)會(huì)從棧中彈出被調(diào)用者的形式參數(shù)和局部變量，釋放被調(diào)用者所占用的數(shù)據(jù)區(qū)，接著被調(diào)用者返回，然后系統(tǒng)從棧中彈出調(diào)用者的返回地址，和實(shí)在參數(shù)等信息，此時(shí)調(diào)用者函數(shù)可以繼續(xù)執(zhí)行下去。

5 求解方法

我們通過舉例來說具體說明遞歸函數(shù)的求解，比如在主函數(shù)中輸入n的值為5，即求5!，則函數(shù)的求解過程可以用圖1-1表示：

以上問題的具體求解過程描述如下：①調(diào)用函數(shù)f(5)，n=5，函數(shù)f(5)的返回結(jié)果是f(4)*5，系統(tǒng)暫存f(5)的形參和中間計(jì)算結(jié)果，然后轉(zhuǎn)去調(diào)用函數(shù)f(4)。②執(zhí)行函數(shù)f(4)，n=4，函數(shù)f(4)的.返回結(jié)果是f(3)*4，系統(tǒng)暫存f(4)的形參和中間計(jì)算結(jié)果，然后轉(zhuǎn)去調(diào)用函數(shù)f(3)。③執(zhí)行函數(shù)f(3)，n=3，函數(shù)f(3)的返回結(jié)果是f(2)*3，系統(tǒng)暫存f(3)的形參和中間計(jì)算結(jié)果，然后轉(zhuǎn)去調(diào)用函數(shù)f(2)。④執(zhí)行函數(shù)f(2)，n=2，函數(shù)f(2)的返回結(jié)果是f(1)*2，系統(tǒng)暫存f(2)的形參和中間計(jì)算結(jié)果，然后轉(zhuǎn)去調(diào)用函數(shù)f(1)。⑤執(zhí)行函數(shù)f(1)，n=1，函數(shù)f(1)返回結(jié)果1，f(1)執(zhí)行完畢，系統(tǒng)釋放f(1)的形參和中間變量所占的數(shù)據(jù)區(qū)，然后返回到調(diào)用函數(shù)f(1)處。⑥函數(shù)f(2)返回結(jié)果f(1)*2=1*2=2，f(2)執(zhí)行完畢，系統(tǒng)釋放f(2)的形參和中間變量所占的數(shù)據(jù)區(qū)，然后返回到調(diào)用函數(shù)f(2)處。⑦函數(shù)f(3)返回結(jié)果f(2)*3=2*3=6，f(3)執(zhí)行完畢，系統(tǒng)釋放f(3)的形參和中間變量所占的數(shù)據(jù)區(qū)，然后返回到調(diào)用函數(shù)f(3)處。⑧函數(shù)f(4)的返回結(jié)果f(3)*4=6*4=24，f(4)執(zhí)行完畢，系統(tǒng)釋放f(4)的形參和中間變量所占的數(shù)據(jù)區(qū)，然后返回到調(diào)用函數(shù)f(4)處。⑨函數(shù)f(5)返回結(jié)果f(4)*5=24*5=120，f(5)執(zhí)行完畢，系統(tǒng)釋放f(5)的形參和中間變量所占的數(shù)據(jù)區(qū)，然后返回到調(diào)用函數(shù)f(5)處，即main函數(shù)，此問題求解結(jié)束。

6 結(jié)束語

函數(shù)的遞歸調(diào)用，可以把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解，遞歸算法只需用少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大減少了程序的代碼量并增強(qiáng)了程序的可讀性。但在求解過程中容易出錯(cuò)和混淆，了解遞歸函數(shù)的執(zhí)行過程，并借助于圖示化的方法、，即可正確、快速求解遞歸函數(shù)。