計算機軟考程序員備考：程序設計知識點(6)

　　6.6 函數遞歸調用

　　一個函數為完成它的復雜工作，可以調用其它別的函數。例如，從主函數出發(fā)，主函數調用函數A() ，函數A()又調用函數B()，函數B()又調用函數C()，等等。這樣從主函數出發(fā)，形成一個長長的調用鏈，就是通常所說的函數嵌套調用。函數嵌套調用時，有一個重要的特征：先被調用的函數后返回。如這里所舉例子，待函數C()完成計算返回后，B()函數繼續(xù)計算(可能還要調用其它函數) ，待計算完成，返回到函數A()，函數A()計算完成后，才返回到主函數。

　　當函數調用鏈上的某兩個函數為同一個函數時，稱這種函數調用方式為遞歸調用。通過速歸調用方式完成其功能的函數稱為遞歸函數。許多問題的求解方法具有遞歸特征，用遞歸函數描述這種求解算法比較簡潔。計算n的階乘(n!)函數就是一個很好的例子。因

　　n! = l*2*3* …*n

　　按其定義用循環(huán)語句可以方便地實現，寫成函數見下例6.5。

　　【例6.5】用循環(huán)實現階乘計算的函數。

　　float fac(int n)

　　{float s;

　　int i;

　　for(s=1.of，i=l;i<=n; i++)

　　s*=1;

　　return s;

　　}

　　然而，把n! 的定義改寫成以下遞歸定義形式

　　(1)n!=1， n<=l;

　　(2)n!= n*(n-1)!， n>l。

　　根據這個定義形式可用遞歸函數描述如下例6.6。

　　【例6.6】 用遞歸實現階乘計算的函數。

　　float rfac(int n)

　　{

　　if( n<=1) return 1.0f;

　　return n*rfac(n-1) ;

　　}

　　以計算3!為例，說明遞歸函數被調用時的執(zhí)行過程。設有代碼m= rfac(3) 調用函數rfac()。函數調用rfac(3) 的計算過程可大致敘述如下：

　　以函數調用rfac(3) 去調用函數rfac() ;函數rfac(n=3) 為計算3*2! ，用rfac(2) 去調用函數rfac();函數rfac(n=2) 為計算2*1!，用rfac(1)去調用函數rfac();函數 rfac(n=1) 計算1! ，以結果1.0返回;返回到發(fā)出調用rfac(1) 處，繼續(xù)計算，得到2! 的結果2.0返回;返回到發(fā)出調用rfac(2) 處，繼續(xù)計算得到3! 的結果6.0返回。

　　遞歸計算n! 有一個重要特征，為求n有關的解，化為求n-l的解，求n-1的解又化為求n-2的解，如此類推。特別地，對于1的解是可立即得到的。這是將大問題解化為小問題解的遞推過程。有了1的解以后，接著是一個回溯過程，逐步獲得2的解，3的解，……，直至n的解。

　　【例6.7】 用遞歸函數實現數組元素的求和計算。

　　要采用遞歸方法計算數組元素的和，可把數組元素的累計和等于當前元素與數組其余元素的和，而對數組其余元素的和通過遞歸實現。下面的函數定義是這樣的解法之一。

　　int rsum(int *a， int n)

　　{

　　if( n==0) return 0;/*若數組沒有元素，則返回0*/

　　return *a+rsum(a+l，n-1);/*當前元素與其余元素的和*/

　　}