C語言中遞歸函數的教學方法探討

孫冬 高清維 盧一相

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

參考文獻：

[1]張建軍，史銀龍，劉勝厚.C語言程序設計[M].北京：海洋出版社，2010：53-63.

[2]譚浩強.C語言程序設計[M].北京：清華大學出版社，1999：35-38.

[3]范勁松，黃友初.案例教學法在C語言教學中的系統應用[J].鄖陽醫學院學報，2005，24（3）：191-192.

[4]王曉東.計算機算法設計與分析[M].北京：電子工業出版社，2010：9-22.