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

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

　　當(dāng)函數(shù)調(diào)用鏈上的某兩個(gè)函數(shù)為同一個(gè)函數(shù)時(shí)，稱這種函數(shù)調(diào)用方式為遞歸調(diào)用。通過(guò)速歸調(diào)用方式完成其功能的函數(shù)稱為遞歸函數(shù)。許多問(wèn)題的求解方法具有遞歸特征，用遞歸函數(shù)描述這種求解算法比較簡(jiǎn)潔。計(jì)算n的階乘(n!)函數(shù)就是一個(gè)很好的例子。因

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

　　按其定義用循環(huán)語(yǔ)句可以方便地實(shí)現(xiàn)，寫成函數(shù)見(jiàn)下例6.5。

　　【例6.5】用循環(huán)實(shí)現(xiàn)階乘計(jì)算的函數(shù)。

　　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。

　　根據(jù)這個(gè)定義形式可用遞歸函數(shù)描述如下例6.6。

　　【例6.6】 用遞歸實(shí)現(xiàn)階乘計(jì)算的函數(shù)。

　　float rfac(int n)

　　{

　　if( n<=1) return 1.0f;

　　return n*rfac(n-1) ;

　　}

　　以計(jì)算3!為例，說(shuō)明遞歸函數(shù)被調(diào)用時(shí)的執(zhí)行過(guò)程。設(shè)有代碼m= rfac(3) 調(diào)用函數(shù)rfac()。函數(shù)調(diào)用rfac(3) 的計(jì)算過(guò)程可大致敘述如下：

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

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

　　【例6.7】 用遞歸函數(shù)實(shí)現(xiàn)數(shù)組元素的求和計(jì)算。

　　要采用遞歸方法計(jì)算數(shù)組元素的和，可把數(shù)組元素的累計(jì)和等于當(dāng)前元素與數(shù)組其余元素的和，而對(duì)數(shù)組其余元素的和通過(guò)遞歸實(shí)現(xiàn)。下面的函數(shù)定義是這樣的解法之一。

　　int rsum(int *a， int n)

　　{

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

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

　　}