- 相關推薦
C語言中遞歸函數的教學方法
導語：函數遞歸基于分治法思想，將復雜的大規(guī)模問題轉化為小規(guī)模問題進行求解，在算法設計中具有重要的理論意義和實用價值，是C語言教學的難點。下面就由小編為大家介紹一下C語言中遞歸函數的教學方法，歡迎大家閱讀!
1.引言
C語言是一種語法簡潔緊湊、運算符豐富、可移植性強、目標程序執(zhí)行效率高的強數據類型語言，近年來在國內得到迅速的推廣應用。作為我校信息類本科教學的入門語言，C語言是匯編語言、計算機原理、單片機程序設計等其他后繼課程的基礎，對整個教學過程具有重要的作用。
所有的C語言程序都由函數組成。在函數的調用中，直接或間接地調用自身的函數稱為遞歸函數，相應的算法稱為遞歸算法。在計算機算法設計與分析中，遞歸算法是一類較重要的算法，遞歸的使用往往使函數的定義和算法的描述簡潔且易于理解。
2.遞歸的基本原理
對于任何可以用計算機求解的問題，其求解難度與計算時間都與問題的規(guī)模有關。若一個規(guī)模較大的且難以直接解決的問題能夠分解為k個規(guī)模較小的子問題，并且這些子問題互相獨立且與原問題相同，那么可以通過對這些子問題進行分別求解，然后將各個子問題的解合并，得到原問題的解。其中P代表原始問題，P1、P2…Pk是比原始問題的規(guī)模|P|更小的子問題，Merge函數將子問題的解y1、y2…yk進行合并。
假設原始問題規(guī)模為n，子問題P1、P2…Pk的規(guī)模為n/m，分解閾值n0=1，且AdHoc函數求解規(guī)模為1的問題耗費1個單位時間。再設合并函數Merge的時間復雜度為f此時遞歸算法具有多項式的計算復雜度，其階數由子問題的劃分數目k和子問題的規(guī)模n/m共同決定。
3.教學實例分析
函數的遞歸是C語言教學中的一個難點，本節(jié)根據上面給出的遞歸程序結構，通過一組從簡單到復雜的實例，逐步引導學生掌握遞歸程序編寫的技巧。
實例1(階乘問題)：計算整數n的階乘。
分析：該問題可使用下述遞歸結構進行求解：
(1)當n=1時，可以直接計算n!=1;
(2)當n>1時，n!可以通過對1個小規(guī)模的子問題(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，規(guī)模n/m = n/2。因為函數Merge的合并操作可以在線性時間內完成，所以由(3)式可以得到相應的時間復雜度為
T(n)=O(nlogn)(4)
4.結語
在C語言教學中，函數的遞歸一直是教學的重點和難點。本文首先從理論上給出遞歸的程序結構，然后以該結構為指導，通過一組程序實例，引導學生掌握遞歸程序的編寫技巧，理解應用分治法解決復雜問題的思想。實踐證明，本方法在課堂教學中取得較好的效果。
【C語言中遞歸函數的教學方法】相關文章：
C語言中遞歸算法的剖析08-15
C語言函數的遞歸調用08-26
C語言函數遞歸教程09-25
C語言函數的遞歸和調用08-22
深入解釋c語言中的遞歸算法07-17
C語言中函數的區(qū)分08-30
c語言中time函數的用法08-27
C語言中gets()函數知識08-10
C語言中strpbr()函數的用法07-25