函數(shù)的遞歸調(diào)用

　　一個(gè)函數(shù)在它的函數(shù)體內(nèi)調(diào)用它自身稱為遞歸調(diào)用。 這種函數(shù)稱為遞歸函數(shù)。C語言允許函數(shù)的遞歸調(diào)用。在遞歸調(diào)用中， 主調(diào)函數(shù)又是被調(diào)函數(shù)。執(zhí)行遞歸函數(shù)將反復(fù)調(diào)用其自身。 每調(diào)用一次就進(jìn)入新的一層。例如有函數(shù)f如下：

　　int f (int x)
　　{
　　int y;
　　z=f(y);
　　return z;
　　}

　　這個(gè)函數(shù)是一個(gè)遞歸函數(shù)。 但是運(yùn)行該函數(shù)將無休止地調(diào)用其自身，這當(dāng)然是不正確的。為了防止遞歸調(diào)用無終止地進(jìn)行， 必須在函數(shù)內(nèi)有終止遞歸調(diào)用的手段。常用的辦法是加條件判斷， 滿足某種條件后就不再作遞歸調(diào)用，然后逐層返回。 下面舉例說明遞歸調(diào)用的執(zhí)行過程。

　　[例5.9]用遞歸法計(jì)算n!用遞歸法計(jì)算n!可用下述公式表示：

　　n!=1 (n=0,1)
　　n×(n-1)! (n>1)
　　按公式可編程如下：
　　long ff(int n)
　　{
　　long f;
　　if(n<0)><0,input error");="">
　　else if(n==0||n==1) f=1;
　　else f=ff(n-1)*n;
　　return(f);
　　}
　　main()
　　{
　　int n;
　　long y;
　　printf("\ninput a inteager number:\n");
　　scanf("%d",&n);
　　y=ff(n);
　　printf("%d!=%ld",n,y);
　　}
　　long ff(int n)
　　{ ……
　　else f=ff(n-1)*n;
　　……
　　}
　　main()
　　{ ……
　　y=ff(n);
　　……
　　}

　　程序中給出的函數(shù)ff是一個(gè)遞歸函數(shù)。主函數(shù)調(diào)用ff 后即進(jìn)入函數(shù)ff執(zhí)行，如果n<0,n==0或n=1時(shí)都將結(jié)束函數(shù)的執(zhí)行，否則就遞歸調(diào)用ff函數(shù)自身。由于每次遞歸調(diào)用的實(shí)參為n-1，即把n-1 的值賦予形參n，最后當(dāng)n-1的值為1時(shí)再作遞歸調(diào)用，形參n的值也為1，將使遞歸終止。然后可逐層退回。下面我們?cè)倥e例說明該過程。="" 設(shè)執(zhí)行本程序時(shí)輸入為5，="" 即求="" 5!。在主函數(shù)中的調(diào)用語句即為y="ff(5)，進(jìn)入ff函數(shù)后，由于n=5,不等于0或1，故應(yīng)執(zhí)行f=ff(n-1)*n,即f=ff(5-1)*5。該語句對(duì)ff作遞歸調(diào)用即ff(4)。" 逐次遞歸展開如圖5.3所示。進(jìn)行四次遞歸調(diào)用后，ff函數(shù)形參取得的值變?yōu)?，故不再繼續(xù)遞歸調(diào)用而開始逐層返回主調(diào)函數(shù)。ff(1)的函數(shù)返回值為1，ff(2)的返回值為1*2="2，ff(3)的返回值為2*3=6，ff(4)" 的返回值為6*4="24，最后返回值ff(5)為24*5=120。">

[1] [2]  下一頁