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