導語：函數遞歸基於分治法思想，將複雜的大規模問題轉化爲小規模問題進行求解，在算法設計中具有重要的理論意義和實用價值，是C語言教學的難點。下面就由小編爲大家介紹一下C語言中遞歸函數的教學方法，歡迎大家閱讀!
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語言教學中，函數的遞歸一直是教學的重點和難點。本文首先從理論上給出遞歸的程序結構，然後以該結構爲指導，通過一組程序實例，引導學生掌握遞歸程序的編寫技巧，理解應用分治法解決複雜問題的思想。實踐證明，本方法在課堂教學中取得較好的效果。
