- 相關(guān)推薦
C語言中遞歸函數(shù)的教學(xué)方法
導(dǎo)語：函數(shù)遞歸基于分治法思想，將復(fù)雜的大規(guī)模問題轉(zhuǎn)化為小規(guī)模問題進(jìn)行求解，在算法設(shè)計中具有重要的理論意義和實(shí)用價值，是C語言教學(xué)的難點(diǎn)。下面就由小編為大家介紹一下C語言中遞歸函數(shù)的教學(xué)方法，歡迎大家閱讀!
C語言中遞歸函數(shù)的教學(xué)方法 1
1.引言
C語言是一種語法簡潔緊湊、運(yùn)算符豐富、可移植性強(qiáng)、目標(biāo)程序執(zhí)行效率高的強(qiáng)數(shù)據(jù)類型語言，近年來在國內(nèi)得到迅速的推廣應(yīng)用。作為我校信息類本科教學(xué)的入門語言，C語言是匯編語言、計算機(jī)原理、單片機(jī)程序設(shè)計等其他后繼課程的基礎(chǔ)，對整個教學(xué)過程具有重要的作用。
所有的C語言程序都由函數(shù)組成。在函數(shù)的調(diào)用中，直接或間接地調(diào)用自身的函數(shù)稱為遞歸函數(shù)，相應(yīng)的算法稱為遞歸算法。在計算機(jī)算法設(shè)計與分析中，遞歸算法是一類較重要的算法，遞歸的使用往往使函數(shù)的定義和算法的'描述簡潔且易于理解。
2.遞歸的基本原理
對于任何可以用計算機(jī)求解的問題，其求解難度與計算時間都與問題的規(guī)模有關(guān)。若一個規(guī)模較大的且難以直接解決的問題能夠分解為k個規(guī)模較小的子問題，并且這些子問題互相獨(dú)立且與原問題相同，那么可以通過對這些子問題進(jìn)行分別求解，然后將各個子問題的解合并，得到原問題的解。其中P代表原始問題，P1、P2…Pk是比原始問題的規(guī)模|P|更小的子問題，Merge函數(shù)將子問題的解y1、y2…yk進(jìn)行合并。
假設(shè)原始問題規(guī)模為n，子問題P1、P2…Pk的規(guī)模為n/m，分解閾值n0=1，且AdHoc函數(shù)求解規(guī)模為1的問題耗費(fèi)1個單位時間。再設(shè)合并函數(shù)Merge的時間復(fù)雜度為f此時遞歸算法具有多項(xiàng)式的計算復(fù)雜度，其階數(shù)由子問題的劃分?jǐn)?shù)目k和子問題的規(guī)模n/m共同決定。
3.教學(xué)實(shí)例分析
函數(shù)的遞歸是C語言教學(xué)中的一個難點(diǎn)，本節(jié)根據(jù)上面給出的遞歸程序結(jié)構(gòu)，通過一組從簡單到復(fù)雜的實(shí)例，逐步引導(dǎo)學(xué)生掌握遞歸程序編寫的技巧。
實(shí)例1(階乘問題)：計算整數(shù)n的階乘。
分析：該問題可使用下述遞歸結(jié)構(gòu)進(jìn)行求解：
(1)當(dāng)n=1時，可以直接計算n!=1;
(2)當(dāng)n>1時，n!可以通過對1個小規(guī)模的子問題(n-1)!的求解得到，也即n!=(n-1)!*n。
實(shí)例2(Hanoi塔問題)：設(shè)a、b、c是三個塔座。開始時，在a座處自上而下、從小到大地疊放n個圓盤，編號分別為1、2、…n，如圖1所示�，F(xiàn)要求將a座處的所有圓盤按同樣的次序堆疊到b座上，并且要求：(1)每次只能移動1個圓盤;(2)任何時候都不允許將大盤壓在小盤的上方。
分析：該問題可使用下述遞歸結(jié)構(gòu)進(jìn)行求解：
(1)當(dāng)n=1時，直接將盤從a座移動到b座;
(2)當(dāng)n>1時，將圓盤按下列方法移動(見圖2)：
�、賹座上的n-1個盤移動到c座;
②將a座的第n個盤移動到b座;
�、蹖座上的n-1個盤移動到b座。
根據(jù)以上分析，可以寫出如下的程序：
實(shí)例3(排序問題)：對n個元素的整型數(shù)組array進(jìn)行排序。
分析：該問題可使用下述遞歸結(jié)構(gòu)進(jìn)行求解：
(1)當(dāng)n=1時，直接輸出排序結(jié)果;
(2)當(dāng)n>1時，按下列方法進(jìn)行排序：
�、賹rray分成大小基本相同的兩部分;
�、趯蓚�子數(shù)組分別進(jìn)行排序;
③將兩個排序后的子數(shù)組進(jìn)行合并。
其中參數(shù)left和right分別代表當(dāng)前數(shù)組的第1個元素和最后一個元素的下標(biāo)。
對于該排序算法，子問題的數(shù)目k=2，規(guī)模n/m = n/2。因?yàn)楹瘮?shù)Merge的合并操作可以在線性時間內(nèi)完成，所以由(3)式可以得到相應(yīng)的時間復(fù)雜度為
T(n)=O(nlogn)(4)
4.結(jié)語
在C語言教學(xué)中，函數(shù)的遞歸一直是教學(xué)的重點(diǎn)和難點(diǎn)。本文首先從理論上給出遞歸的程序結(jié)構(gòu)，然后以該結(jié)構(gòu)為指導(dǎo)，通過一組程序?qū)嵗�，引�?dǎo)學(xué)生掌握遞歸程序的編寫技巧，理解應(yīng)用分治法解決復(fù)雜問題的思想。實(shí)踐證明，本方法在課堂教學(xué)中取得較好的效果。
C語言中遞歸函數(shù)的教學(xué)方法 2
【示例】用遞歸計算 n!。階乘 n! 的計算公式如下：
根據(jù)公式編程：
long factorial(int n){
long result;
if(n==0 || n==1){
result = 1;
}else{
result = factorial(n-1) * n; // 遞歸調(diào)用
}
return result;
}
這是一個典型的遞歸函數(shù)。調(diào)用factorial后即進(jìn)入函數(shù)體，只有當(dāng) n==0 或 n==1 時函數(shù)才會執(zhí)行結(jié)束，否則就一直調(diào)用它自身。
由于每次調(diào)用的實(shí)參為 n-1，即把 n-1 的值賦給形參 n，所以每次遞歸實(shí)參的值都減 1，直到最后 n-1 的值為 1 時再作遞歸調(diào)用，形參 n 的值也為1，遞歸就終止了，會逐層退出。
例如求 5!，即調(diào)用factorial(5)。當(dāng)進(jìn)入factorial函數(shù)體后，由于 n=5，不等于0或1，所以執(zhí)行result = factorial(n-1) * n;，即result = factorial(5-1) * 5;，接下來也就是調(diào)用factorial(4)。這是第一次遞歸。
進(jìn)行四次遞歸調(diào)用后，實(shí)參的值為 1，也就是調(diào)用factorial(1)。這時遞歸就結(jié)束了，開始逐層返回。factorial(1) 的值為 1，factorial(2) 的值為 1*2=2，factorial(3) 的'值為 2*3=6，factorial(4) 的值為 6*4=24，最后返回值 factorial(5) 為 24*5=120。
注意：為了防止遞歸調(diào)用無終止地進(jìn)行，必須在函數(shù)內(nèi)有終止遞歸調(diào)用的手段。常用的辦法是加條件判斷，滿足某種條件后就不再作遞歸調(diào)用，然后逐層返回。
遞歸調(diào)用不但難于理解，而且開銷很大，如非必要，不推薦使用遞歸。很多遞歸調(diào)用可以用迭代（循環(huán)）來代替。
【示例】用迭代法求 n!。
復(fù)制純文本新窗口
long factorial(int n){
int i;
long result=1;
if(n==0 || n==1){
return 1;
}
for(i=1; i<=n; i++){
result *= i;
}
return result;
}
C語言中遞歸函數(shù)的教學(xué)方法 3
一、要點(diǎn)：
1、C語言函數(shù)可以遞歸調(diào)用。
2、可以通過直接或間接兩種方式調(diào)用。目前只討論直接遞歸調(diào)用。
二、遞歸條件
采用遞歸方法來解決問題，必須符合以下三個條件：
1、可以把要解決的問題轉(zhuǎn)化為一個新問題，而這個新的問題的解決方法仍與原來的解決方法相同，只是所處理的對象有規(guī)律地遞增或遞減。
說明：解決問題的方法相同，調(diào)用函數(shù)的參數(shù)每次不同(有規(guī)律的遞增或遞減)，如果沒有規(guī)律也就不能適用遞歸調(diào)用。
2、可以應(yīng)用這個轉(zhuǎn)化過程使問題得到解決。
說明：使用其他的辦法比較麻煩或很難解決，而使用遞歸的方法可以很好地解決問題。
3、必定要有一個明確的結(jié)束遞歸的條件。
說明：一定要能夠在適當(dāng)?shù)牡胤浇Y(jié)束遞歸調(diào)用。不然可能導(dǎo)致系統(tǒng)崩潰。
三、遞歸實(shí)例
例：使用遞歸的方法求n!
當(dāng)n>1時，求n!的問題可以轉(zhuǎn)化為n*(n-1)!的新問題。
比如n=5：
第一部分：5*4*3*2*1 n*(n-1)!
第二部分：4*3*2*1 (n-1)*(n-2)!
第三部分：3*2*1 (n-2)(n-3)!
第四部分：2*1 (n-3)(n-4)!
第五部分：1 (n-5)! 5-5=0，得到值1，結(jié)束遞歸。
源程序：
fac(int n)
{int t;
if(n==1)||(n==0) return 1;
else
{ t=n*fac(n-1);
return t;
}
}
main( )
{int m,y;
printf(“Enter m:”);
scanf(“%d”,&m);
if(m<0) printf(“Input data Error!n”);
else
{y=fac(m);
printf(“n%d! =%d n”,m,y);
}
}
四、遞歸說明
1、當(dāng)函數(shù)自己調(diào)用自己時，系統(tǒng)將自動把函數(shù)中當(dāng)前的變量和形參暫時保留起來，在新一輪的調(diào)用過程中，系統(tǒng)為新調(diào)用的函數(shù)所用到的`變量和形參開辟另外的存 儲單元(內(nèi)存空間)。每次調(diào)用函數(shù)所使用的變量在不同的內(nèi)存空間。
2、遞歸調(diào)用的層次越多，同名變量的占用的存儲單元也就越多。一定要記住，每次函數(shù)的調(diào)用，系統(tǒng)都會為該函數(shù)的變量開辟新的內(nèi)存空間。
3、當(dāng)本次調(diào)用的函數(shù)運(yùn)行結(jié)束時，系統(tǒng)將釋放本次調(diào)用時所占用的內(nèi)存空間。程序的流程返回到上一層的調(diào)用點(diǎn)，同時取得當(dāng)初進(jìn)入該層時，函數(shù)中的變量和形參 所占用的內(nèi)存空間的數(shù)據(jù)。
4、所有遞歸問題都可以用非遞歸的方法來解決，但對于一些比較復(fù)雜的遞歸問題用非遞歸的方法往往使程序變得十分復(fù)雜難以讀懂，而函數(shù)的遞歸調(diào)用在解決這類 問題時能使程序簡潔明了有較好的可讀性;但由于遞歸調(diào)用過程中，系統(tǒng)要為每一層調(diào)用中的變量開辟內(nèi)存空間、要記住每一層調(diào)用后的返回點(diǎn)、要增加許多額外的 開銷，因此函數(shù)的遞歸調(diào)用通常會降低程序的運(yùn)行效率。
五、程序流程
fac(int n) /*每次調(diào)用使用不同的參數(shù)*/
{ int t; /*每次調(diào)用都會為變量t開辟不同的內(nèi)存空間*/
if(n==1)||(n==0) /*當(dāng)滿足這些條件返回1 */
return 1;
else
{ t=n*fac(n-1); /*每次程序運(yùn)行到此處就會用n-1作為參數(shù)再調(diào)用一次本函數(shù),此處是調(diào)用點(diǎn)*/
return t; /*只有在上一句調(diào)用的所有過程全部結(jié)束時才運(yùn)行到此處。*/
}
}
【C語言中遞歸函數(shù)的教學(xué)方法】相關(guān)文章：
C語言函數(shù)遞歸教程09-25
C語言中遞歸算法的剖析08-15
對C語言中遞歸算法的深入解析09-26
深入解釋c語言中的遞歸算法07-17
C語言中函數(shù)的區(qū)分08-30