函數的遞歸調用

　　一個函數在它的函數體內調用它自身稱為遞歸調用。 這種函數稱為遞歸函數。C語言允許函數的遞歸調用。在遞歸調用中， 主調函數又是被調函數。執行遞歸函數將反復調用其自身。 每調用一次就進入新的一層。例如有函數f如下：

　　int f (int x)

　　{

　　int y;

　　z=f(y);

　　return z;

　　}

　　這個函數是一個遞歸函數。 但是運行該函數將無休止地調用其自身，這當然是不正確的。為了防止遞歸調用無終止地進行， 必須在函數內有終止遞歸調用的手段。常用的辦法是加條件判斷， 滿足某種條件后就不再作遞歸調用，然后逐層返回。 下面舉例說明遞歸調用的執行過程。

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

　　n!=1 (n=0,1)

　　n×(n-1)! (n>1)

　　按公式可編程如下：

　　long ff(int n)

　　{

　　long f;

　　if(n<0) printf("n<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);

　　……

　　}

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

　　例5. 9也可以不用遞歸的方法來完成。如可以用遞推法，即從1開始乘以2，再乘以3…直到n。遞推法比遞歸法更容易理解和實現。但是有些問題則只能用遞歸算法才能實現。典型的問題是Hanoi塔問題。

　　[例5.10]Hanoi塔問題

　　一塊板上有三根針，A，B，C。A針上套有64個大小不等的圓盤， 大的在下，小的在上。如圖5.4所示。要把這64個圓盤從A針移動C針上，每次只能移動一個圓盤，移動可以借助B針進行。但在任何時候，任何針上的圓盤都必須保持大盤在下，小盤在上。求移動的步驟。

　　相關推薦：

　　2012年軟考系統分析師考試60天完美復習計劃

　　2012年軟件水平考試網絡工程師章節筆記講義匯總

　　2012年上半年軟件水平考試成績查詢匯總