- 相關(guān)推薦
C語(yǔ)言遞歸函數的執行與求解
導語(yǔ)：函數的遞歸調用是在調用一個(gè)函數的執行過(guò)程中，直接或間接地調用該函數本身，使用遞歸函數的程序結構清晰，簡(jiǎn)單、易懂。下面就由小編為大家介紹一下C語(yǔ)言遞歸函數的執行與求解，歡迎大家閱讀!
1 遞歸函數
C語(yǔ)言的特點(diǎn)之一就在于允許函數的遞歸調用，即允許在函數內部直接或間接的調用函數自身，被調用的函數被稱(chēng)為遞歸函數。遞歸調用有直接遞歸調用和間接遞歸調用兩種形式，遞歸函數常用于解決那些需要分多次求解且每次求解過(guò)程都基本類(lèi)似的問(wèn)題。構造遞歸函數的關(guān)鍵在于尋找遞歸算法和終結條件。遞歸算法就是解決問(wèn)題所采取的方法和步驟，一般只要對問(wèn)題的若干次求解過(guò)程進(jìn)行分析和歸納，找出每一次求解過(guò)程之間的規律性，就可歸納出遞歸算法，終結條件是為了終結函數的遞歸調用而設置的一個(gè)條件或規則。遞歸調用的一般形式為：
函數類(lèi)型 函數名(參數列表)
{
，，，，，
函數名(參數列表)
…..
}
2 遞歸條件
使用遞歸調用編寫(xiě)程序時(shí)，要注意以下幾點(diǎn)：
(1)可以通過(guò)遞歸調用來(lái)縮小問(wèn)題規模，且新問(wèn)題與原問(wèn)題有著(zhù)相同的形式，只是所處理的對象具有一定的規律性。也就是說(shuō)解決問(wèn)題的方法相同，調用函數的參數有規律的遞增或遞減。
(2)遞歸函數必須有一個(gè)終止處理條件，即必須有一個(gè)明確的結束條件，必須在適當的時(shí)候能夠結束遞歸調用，否則會(huì )使程序陷入死循環(huán)，導致系統崩潰。
(3)有些使用遞歸算法求解的問(wèn)題也可使用普通循環(huán)算法來(lái)實(shí)現，相較于循環(huán)程序，遞歸程序結構簡(jiǎn)單，邏輯清晰，但運行效率低，故在有其他算法可以代替的情況下，要盡量避免使用遞歸算法編寫(xiě)程序。
3 遞歸實(shí)例
例：使用遞歸方法求n!。
在數學(xué)上n!=1×2×3×…×n-1×n，我們可以寫(xiě)成以下形式
1 當n=0或n=1時(shí)
n!=
(n-1)!×n 當n>1時(shí)
根據以上形式，可以寫(xiě)出如下遞歸調用程序：
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 遞歸函數執行過(guò)程
遞歸調用之所以能夠實(shí)現，是因為函數在每一次執行過(guò)程中，都會(huì )把自己所有形參變量和局部變量復制一個(gè)副本，壓入棧中，這些副本分別位于棧中不同的內存空間，和函數的其他執行過(guò)程毫不相干，這種機制使得遞歸調用成為可能。一個(gè)遞歸函數的執行過(guò)程類(lèi)似于調用函數和被調用函數是同一個(gè)函數的多層嵌套調用，因此，和遞歸函數的執行過(guò)程密切相關(guān)的一個(gè)重要概念就是遞歸函數運行的層次。假設調用該遞歸函數的主函數為第0層，則從主函數調用遞歸函數則進(jìn)入第一層;從第n層調用本函數則進(jìn)入“下一層”，即第n+1層。反之，退出第n層遞歸調用應返回至“上一層”，即第n-1層。
在遞歸函數的執行過(guò)程中，另一個(gè)非常重要的概念是“遞歸工作�！钡氖褂�，當一個(gè)函數(調用者)調用另外一個(gè)函數(被調用者)時(shí)，系統會(huì )把調用者的所有實(shí)在參數，被調用者的形式參數、局部變量，以及調用者的返回地址等信息全部壓入“遞歸工作�！睍捍�，當被調用者執行完畢時(shí)，系統會(huì )從棧中彈出被調用者的形式參數和局部變量，釋放被調用者所占用的數據區，接著(zhù)被調用者返回，然后系統從棧中彈出調用者的返回地址，和實(shí)在參數等信息，此時(shí)調用者函數可以繼續執行下去。
5 求解方法
我們通過(guò)舉例來(lái)說(shuō)具體說(shuō)明遞歸函數的求解，比如在主函數中輸入n的值為5，即求5!，則函數的求解過(guò)程可以用圖1-1表示：
以上問(wèn)題的具體求解過(guò)程描述如下：①調用函數f(5)，n=5，函數f(5)的返回結果是f(4)*5，系統暫存f(5)的形參和中間計算結果，然后轉去調用函數f(4)。②執行函數f(4)，n=4，函數f(4)的返回結果是f(3)*4，系統暫存f(4)的形參和中間計算結果，然后轉去調用函數f(3)。③執行函數f(3)，n=3，函數f(3)的返回結果是f(2)*3，系統暫存f(3)的形參和中間計算結果，然后轉去調用函數f(2)。④執行函數f(2)，n=2，函數f(2)的返回結果是f(1)*2，系統暫存f(2)的形參和中間計算結果，然后轉去調用函數f(1)。⑤執行函數f(1)，n=1，函數f(1)返回結果1，f(1)執行完畢，系統釋放f(1)的形參和中間變量所占的數據區，然后返回到調用函數f(1)處。⑥函數f(2)返回結果f(1)*2=1*2=2，f(2)執行完畢，系統釋放f(2)的形參和中間變量所占的數據區，然后返回到調用函數f(2)處。⑦函數f(3)返回結果f(2)*3=2*3=6，f(3)執行完畢，系統釋放f(3)的形參和中間變量所占的數據區，然后返回到調用函數f(3)處。⑧函數f(4)的返回結果f(3)*4=6*4=24，f(4)執行完畢，系統釋放f(4)的形參和中間變量所占的數據區，然后返回到調用函數f(4)處。⑨函數f(5)返回結果f(4)*5=24*5=120，f(5)執行完畢，系統釋放f(5)的形參和中間變量所占的數據區，然后返回到調用函數f(5)處，即main函數，此問(wèn)題求解結束。
6 結束語(yǔ)
函數的遞歸調用，可以把一個(gè)大型復雜的問(wèn)題層層轉化為一個(gè)與原問(wèn)題相似的規模較小的問(wèn)題來(lái)求解，遞歸算法只需用少量的程序就可描述出解題過(guò)程所需要的多次重復計算，大大減少了程序的代碼量并增強了程序的可讀性。但在求解過(guò)程中容易出錯和混淆，了解遞歸函數的執行過(guò)程，并借助于圖示化的方法、，即可正確、快速求解遞歸函數。
【C語(yǔ)言遞歸函數的執行與求解】相關(guān)文章：
C語(yǔ)言函數遞歸教程03-01
C語(yǔ)言函數的遞歸調用05-17
C語(yǔ)言函數的遞歸和調用05-09
C語(yǔ)言中遞歸算法的剖析08-15
深入解釋c語(yǔ)言中的遞歸算法07-17
對C語(yǔ)言中遞歸算法的深入解析02-27
淺談C語(yǔ)言函數03-28