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