孫冬 高清維 盧一相

摘 要： 函數(shù)遞歸基于分治法思想，將復(fù)雜的大規(guī)模問(wèn)題轉(zhuǎn)化為小規(guī)模問(wèn)題進(jìn)行求解，在算法設(shè)計(jì)中具有重要的理論意義和實(shí)用價(jià)值，是C語(yǔ)言教學(xué)的難點(diǎn)。通過(guò)一組從簡(jiǎn)單到復(fù)雜的程序?qū)嵗龑?dǎo)學(xué)生由淺入深地掌握遞歸程序的編寫(xiě)技巧，在教學(xué)中取得較好的效果。

關(guān)鍵詞： C語(yǔ)言 遞歸函數(shù) 分治法思想 教學(xué)方法

1.引言

C語(yǔ)言是一種語(yǔ)法簡(jiǎn)潔緊湊、運(yùn)算符豐富、可移植性強(qiáng)、目標(biāo)程序執(zhí)行效率高的強(qiáng)數(shù)據(jù)類(lèi)型語(yǔ)言，近年來(lái)在國(guó)內(nèi)得到迅速的推廣應(yīng)用。作為我校信息類(lèi)本科教學(xué)的入門(mén)語(yǔ)言，C語(yǔ)言是匯編語(yǔ)言、計(jì)算機(jī)原理、單片機(jī)程序設(shè)計(jì)等其他后繼課程的基礎(chǔ)，對(duì)整個(gè)教學(xué)過(guò)程具有重要的作用。

所有的C語(yǔ)言程序都由函數(shù)組成。在函數(shù)的調(diào)用中，直接或間接地調(diào)用自身的函數(shù)稱(chēng)為遞歸函數(shù)，相應(yīng)的算法稱(chēng)為遞歸算法。在計(jì)算機(jī)算法設(shè)計(jì)與分析中，遞歸算法是一類(lèi)較重要的算法，遞歸的使用往往使函數(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é)生掌握遞歸程序編寫(xiě)的技巧。

實(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è)塔座。開(kāi)始時(shí)，在a座處自上而下、從小到大地疊放n個(gè)圓盤(pán)，編號(hào)分別為1、2、…n，如圖1所示?，F(xiàn)要求將a座處的所有圓盤(pán)按同樣的次序堆疊到b座上，并且要求：（1）每次只能移動(dòng)1個(gè)圓盤(pán)；（2）任何時(shí)候都不允許將大盤(pán)壓在小盤(pán)的上方。

分析：該問(wèn)題可使用下述遞歸結(jié)構(gòu)進(jìn)行求解：

（1）當(dāng)n=1時(shí)，直接將盤(pán)從a座移動(dòng)到b座；

（2）當(dāng)n>1時(shí)，將圓盤(pán)按下列方法移動(dòng)（見(jiàn)圖2）：

①將a座上的n-1個(gè)盤(pán)移動(dòng)到c座；

②將a座的第n個(gè)盤(pán)移動(dòng)到b座；

③將c座上的n-1個(gè)盤(pán)移動(dòng)到b座。

根據(jù)以上分析，可以寫(xiě)出如下的程序：

實(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)行排序：

①將array分成大小基本相同的兩部分；

②對(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的合并操作可以在線(xiàn)性時(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é)生掌握遞歸程序的編寫(xiě)技巧，理解應(yīng)用分治法解決復(fù)雜問(wèn)題的思想。實(shí)踐證明，本方法在課堂教學(xué)中取得較好的效果。

參考文獻(xiàn)：

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

[2]譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，1999：35-38.

[3]范勁松，黃友初.案例教學(xué)法在C語(yǔ)言教學(xué)中的系統(tǒng)應(yīng)用[J].鄖陽(yáng)醫(yī)學(xué)院學(xué)報(bào)，2005，24（3）：191-192.

[4]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2010：9-22.