余艷　劉燕麗

摘要：學(xué)生對遞歸算法的理解和掌握程度影響著對數(shù)據(jù)結(jié)構(gòu)及后續(xù)課程的學(xué)習(xí)效果，提出在數(shù)據(jù)結(jié)構(gòu)課程中應(yīng)補(bǔ)充遞歸思想和算法實(shí)現(xiàn)的教學(xué)，探討了教學(xué)要點(diǎn)和教學(xué)方法，并設(shè)計(jì)合理的實(shí)驗(yàn)教學(xué)方案。實(shí)踐證明教改后取得了良好的教學(xué)效果。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；遞歸算法；教學(xué)要點(diǎn)；教學(xué)方法

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）04-0784-04

數(shù)據(jù)結(jié)構(gòu)課程教學(xué)內(nèi)容中無論是概念的描述還是算法的設(shè)計(jì)，都廣泛使用了遞歸的思想。以嚴(yán)蔚敏的數(shù)據(jù)結(jié)構(gòu)教材[1]為例，在概念的描述上，廣義表、二叉樹、樹的定義都使用了遞歸的形式；在算法設(shè)計(jì)上，二叉樹的先序、中序和后序遍歷、二叉樹的構(gòu)造、樹的先根和后根遍歷、圖的深度優(yōu)先搜索、二叉排序樹上的查找以及排序算法中的快速排序和遞歸排序均使用了遞歸的方法。

數(shù)據(jù)結(jié)構(gòu)和遞歸思想密不可分，學(xué)生對遞歸算法的理解和掌握程度影響著對數(shù)據(jù)結(jié)構(gòu)及后續(xù)課程的學(xué)習(xí)效果，因此教學(xué)工作者們對遞歸算法的教學(xué)方法做了大量探索和研究。文獻(xiàn)[2]指出應(yīng)提前引入簡單問題遞歸算法的講解，為后續(xù)復(fù)雜問題的遞歸算法教學(xué)鋪平道路，并給出線性表上遞歸算法的教學(xué)示例。文獻(xiàn)[3]指出學(xué)生由于不清楚遞歸函數(shù)的執(zhí)行過程影響了對遞歸算法的理解，舉例使用圖示法解析了函數(shù)調(diào)用過程中棧的變化和遞歸函數(shù)的執(zhí)行過程。文[4]強(qiáng)調(diào)在教學(xué)過程中應(yīng)先講解學(xué)生容易理解的數(shù)值型遞歸問題，再討論非數(shù)值型遞歸問題。文獻(xiàn)[5，6]給出了包括遞歸模型、遞歸原理、遞歸程序的閱讀和遞歸程序的設(shè)計(jì)四個(gè)環(huán)節(jié)的教學(xué)過程。該文以武漢科技大學(xué)信息與計(jì)算科學(xué)系為例，分析在數(shù)據(jù)結(jié)構(gòu)遞歸相關(guān)內(nèi)容的教學(xué)環(huán)節(jié)中常遇到的問題，提出在數(shù)據(jù)結(jié)構(gòu)教學(xué)中應(yīng)補(bǔ)充對遞歸思想和算法實(shí)現(xiàn)的講授與實(shí)驗(yàn)安排，教學(xué)過程應(yīng)由淺入深、由表及里、提前引入、貫穿始終，探討了遞歸算法編寫思路、運(yùn)行機(jī)制和使用場合的教學(xué)方法，并設(shè)計(jì)相應(yīng)的實(shí)驗(yàn)教學(xué)方案。

1 數(shù)據(jù)結(jié)構(gòu)遞歸算法教學(xué)中存在的問題

1）從課堂教學(xué)的學(xué)生反應(yīng)來看，學(xué)生對使用遞歸方式描述的概念進(jìn)行正確理解通常問題不大；但數(shù)據(jù)結(jié)構(gòu)中使用遞歸算法解決的問題大多比較復(fù)雜，學(xué)生對這些遞歸算法的閱讀依然感到吃力，這些算法中的遞歸策略影響了學(xué)生對算法問題本身的理解；

2）在用到遞歸算法的實(shí)驗(yàn)中常有學(xué)生表示對遞歸算法能夠?qū)崿F(xiàn)預(yù)期功能感到不可思議；

3）在需要自行編寫遞歸算法求解問題時(shí)常有學(xué)生不知如何下手。

2 遞歸算法及實(shí)現(xiàn)的教學(xué)要點(diǎn)

學(xué)生在前導(dǎo)課程高級程序設(shè)計(jì)語言的學(xué)習(xí)中曾經(jīng)接觸過幾個(gè)遞歸算法，但學(xué)生只有粗略印象并沒有深入學(xué)習(xí)。在廣泛使用的嚴(yán)蔚敏的數(shù)據(jù)結(jié)構(gòu)教材[1]中，“棧與遞歸的實(shí)現(xiàn)”為選講內(nèi)容，根據(jù)多年教學(xué)經(jīng)驗(yàn)來看，如果教學(xué)過程越過該內(nèi)容，后續(xù)出現(xiàn)的一系列遞歸算法往往常成為教學(xué)過程中的絆腳石，因此有必要安排專門的課時(shí)對遞歸算法的編寫思路、運(yùn)行機(jī)制展開講解，并輔以必要的實(shí)驗(yàn)練習(xí)用于鞏固。

雖然遞歸算法形式簡潔，但對初學(xué)者來說由于遞歸算法在執(zhí)行過程中會(huì)層層調(diào)用自身且執(zhí)行過程不直觀，使初學(xué)者對遞歸算法的執(zhí)行過程感到困惑不解。依據(jù)教學(xué)經(jīng)驗(yàn)來看，如果直接向?qū)W生講解遞歸算法執(zhí)行過程，以及系統(tǒng)在代碼背后完成的一系列工作諸如開辟遞歸工作棧等常使得學(xué)生對遞歸算法感到高深莫測和枯燥乏味。如果先引導(dǎo)學(xué)生觀摩遞歸算法的經(jīng)典實(shí)例并傳授遞歸算法編寫的思路，使學(xué)生對遞歸算法先有個(gè)感性認(rèn)識(shí)且能夠?qū)π碌膯栴}進(jìn)行分析并自行編寫出遞歸算法，則可以為學(xué)生建立信心并產(chǎn)生對遞歸算法進(jìn)一步探索的興趣；然后再引導(dǎo)學(xué)生洞悉遞歸算法執(zhí)行的內(nèi)部機(jī)制，從而達(dá)到知其然且知其所以然。因此將遞歸算法的教學(xué)過程分為三個(gè)步驟：1）傳授遞歸算法的編寫思路；2）洞悉遞歸算法的實(shí)現(xiàn)機(jī)制；3）分析遞歸算法的使用場合。

2.1 遞歸算法的編寫思路

遞歸是一種分析和解決問題的方法和思想，從形式上來看它是函數(shù)直接或間接地調(diào)用自己。當(dāng)待解決的問題滿足以下兩個(gè)條件，則可用遞歸方法求解：1）問題可以分解為規(guī)模更小但與原問題性質(zhì)相同的子問題；2）具備遞歸終止條件。下面直接通過例子來學(xué)習(xí)遞歸算法的編寫方法。

例1：計(jì)算n階乘，其中n為非負(fù)整數(shù)。

算法思路：由于5！=5×4×3×2×1， 4！=4×3×2×1，可以推得n！=n×（n-1）！。其中求解（n-1）！與（n）！是性質(zhì)相同的問題，但規(guī)模變小了；且0！=1，1！=1，它們構(gòu)成了遞歸調(diào)用的終止條件。故n階乘問題可以用遞歸算法求解，如下所示：

int Fac（int n）{

if （n==0||n==1）

return 1；

else

return n*Fac（n-1）；

}

例2：逆序輸出單鏈表。已知單鏈表不帶頭結(jié)點(diǎn)，結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)定義為

typedef struct Node{

int data；

struct Node *next；

}Node；

算法思路：逆序輸出整個(gè)單鏈表，可以考慮先逆序輸出后n-1個(gè)元素，再輸出第一個(gè)元素。其中逆序輸出后n-1個(gè)元素與原問題是性質(zhì)相同的問題，且規(guī)模更??；若單鏈表為空，則為空操作，它構(gòu)成了遞歸調(diào)用的終止條件。故逆序輸出單鏈表可以用遞歸算法求解，如下所示：

void RevPrint（Node *p）{

if （p）{

RevPrint（p→next）；

printf（"%d "，p→data）；

}

}

2.2 遞歸算法的實(shí)現(xiàn)機(jī)制

2.2.1 遞歸算法的調(diào)用流程

遞歸算法形式簡潔但執(zhí)行過程并不直觀，使得初學(xué)者對遞歸調(diào)用的流程理解困難，尤其對函數(shù)調(diào)用和返回的對象與時(shí)機(jī)容易理解錯(cuò)誤。遞歸調(diào)用流程的講解通?？梢圆捎脛?dòng)態(tài)演示法或者是圖示法。動(dòng)態(tài)演示法利用程序調(diào)試工具通過設(shè)置斷點(diǎn)和單步執(zhí)行等手段來展現(xiàn)算法執(zhí)行的各個(gè)步驟，但由于程序執(zhí)行細(xì)節(jié)過多，學(xué)生如果在某一個(gè)環(huán)節(jié)沒有跟上，就很難對整個(gè)執(zhí)行過程理解到位。因此對遞歸調(diào)用流程的講解更推薦采用圖示法。

如圖1所示，演示了n階乘遞歸算法的調(diào)用流程，使用遞歸算法求解3階乘。圖中實(shí)線代表遞歸調(diào)用，實(shí)線的起始端對應(yīng)函數(shù)調(diào)用語句，箭頭端代表進(jìn)入被調(diào)用的函數(shù)體；虛線代表被調(diào)用函數(shù)執(zhí)行完畢并返回至調(diào)用語句處；實(shí)線和虛線上的編號(hào)代表函數(shù)調(diào)用和返回的次序。代碼左側(cè)序號(hào)為語句行號(hào)。由圖示可知，遞歸調(diào)用遵循先調(diào)用后返回的特點(diǎn)，且最后一次調(diào)用滿足遞歸的終止條件，使得程序不會(huì)無限制的遞歸下去。

圖1 3階乘的遞歸調(diào)用流程

2.2.2 遞歸工作棧

當(dāng)學(xué)生弄清楚遞歸調(diào)用的流程、自己也可以動(dòng)手編寫遞歸程序以后，自然會(huì)進(jìn)一步思索遞歸程序表面看起來井井有序的調(diào)用工作到底是怎樣實(shí)現(xiàn)的，這便是該引出遞歸工作棧的時(shí)候了。首先介紹普通函數(shù)調(diào)用期間系統(tǒng)所做工作，再引出遞歸調(diào)用時(shí)系統(tǒng)完成的工作，并以階乘的遞歸算法為例形象展示遞歸調(diào)用期間系統(tǒng)協(xié)助完成的工作。通過該部分的講解可以排除學(xué)生對遞歸調(diào)用的神秘感。

1）普通函數(shù)調(diào)用

程序運(yùn)行期間發(fā)生函數(shù)調(diào)用時(shí)系統(tǒng)需要為其分配存儲(chǔ)空間，用于保存外層函數(shù)的實(shí)參和返回地址、內(nèi)層函數(shù)的局部變量等；調(diào)用函數(shù)執(zhí)行期間，則該存儲(chǔ)區(qū)保存的局部變量參與運(yùn)算；調(diào)用函數(shù)執(zhí)行完畢時(shí)，則根據(jù)該存儲(chǔ)空間保存的返回地址返回到被調(diào)用函數(shù)，并釋放該存儲(chǔ)空間。當(dāng)多個(gè)函數(shù)嵌套調(diào)用時(shí)，需要按照“后調(diào)用先返回”的原則保證程序邏輯的完備，為實(shí)現(xiàn)這一原則系統(tǒng)通常采用“?！苯Y(jié)構(gòu)來實(shí)現(xiàn)前述存儲(chǔ)空間的分配。具體來講，系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，就為它在棧頂分配一個(gè)存儲(chǔ)區(qū)，每當(dāng)一個(gè)函數(shù)退出時(shí)，就釋放它的存儲(chǔ)區(qū)，棧頂總是存放當(dāng)前正運(yùn)行的函數(shù)的相關(guān)信息。

2）遞歸函數(shù)調(diào)用

遞歸函數(shù)調(diào)用和普通函數(shù)調(diào)用本質(zhì)上并沒有區(qū)別，只不過每次調(diào)用的是同一個(gè)函數(shù)體而已。為區(qū)分各次調(diào)用，調(diào)用遞歸函數(shù)的主函數(shù)稱為第0層，則從主函數(shù)調(diào)用遞歸函數(shù)稱為進(jìn)入第1層；從第i層遞歸調(diào)用遞歸函數(shù)稱為進(jìn)入第i+1層。通常把遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲(chǔ)區(qū)稱作遞歸工作棧，每一次遞歸調(diào)用會(huì)產(chǎn)生一條“工作記錄”，包含調(diào)用時(shí)所需要的實(shí)參、局部變量和返回地址。每進(jìn)入一層遞歸調(diào)用，就產(chǎn)生一條新的工作記錄壓入棧頂，每退出一層遞歸，就從棧頂彈出一條工作記錄[1]，并按所保存的返回地址進(jìn)行返回，從而實(shí)現(xiàn)了遞歸程序最后調(diào)用最先返回的特性。由此可知，在每一層的調(diào)用過程中，系統(tǒng)為新調(diào)用的函數(shù)所用到的局部變量開辟新的的存儲(chǔ)空間，每次調(diào)用所使用的局部變量在不同的存儲(chǔ)空間。

3）遞歸工作棧示例

如表1所示，以3階乘的遞歸求解為例演示了遞歸工作棧的狀態(tài)變化。遞歸工作棧中的工作記錄包括被調(diào)用函數(shù)的返回地址和調(diào)用函數(shù)的局部變量，其中返回地址使用程序語句所在行號(hào)表示，并假設(shè)主函數(shù)的返回地址為0，程序語句所在行號(hào)詳見圖1。

2.3 遞歸算法的使用場合

通過前面的學(xué)習(xí)，學(xué)生將感受到使用遞歸的思想解決問題可以使求解思路簡單清晰，而且編寫出的代碼精簡易讀，遞歸層層調(diào)用和返回的工作交給系統(tǒng)完成就可以了。那么滿足遞歸兩個(gè)條件的問題是否都應(yīng)該使用遞歸算法來求解呢？要回答這個(gè)問題，則需要從函數(shù)調(diào)用的代價(jià)來考慮。

由上節(jié)討論可知發(fā)生函數(shù)調(diào)用時(shí)系統(tǒng)需要保存當(dāng)前的調(diào)用現(xiàn)場，為其分配存儲(chǔ)空間，調(diào)用函數(shù)執(zhí)行完畢時(shí)需要返回被調(diào)用處并釋放該存儲(chǔ)空間，因此函數(shù)調(diào)用的過程既浪費(fèi)系統(tǒng)存儲(chǔ)空間，還消耗系統(tǒng)處理的時(shí)間。遞歸算法通常需要進(jìn)行多次的函數(shù)調(diào)用，因此遞歸算法會(huì)浪費(fèi)很多時(shí)間在函數(shù)調(diào)用的處理上。當(dāng)遞歸層次較深時(shí)，甚至可能造成棧溢出的問題。

那么對于同一個(gè)問題如果既可以使用遞歸算法求解，又可以使用迭代算法求解 ，例如n階乘問題，盡管遞歸可以簡化求解思路，但空間和時(shí)間上的開銷卻更大，此時(shí)我們更傾向于選擇使用迭代方法求解。當(dāng)然，有些問題使用迭代算法很難甚至解決不了，例如經(jīng)典的漢諾塔問題，這時(shí)我們就必須求助于遞歸算法了。

3 遞歸算法實(shí)驗(yàn)內(nèi)容設(shè)置

單純依靠課堂的講授不足以使學(xué)生熟練掌握遞歸思想的使用方法，仍然需要依靠實(shí)驗(yàn)練習(xí)來加深學(xué)生對遞歸的理解、鞏固遞歸算法的編寫和調(diào)試方法。實(shí)驗(yàn)教學(xué)內(nèi)容的合理設(shè)置和精心安排更有利于學(xué)生建立學(xué)習(xí)的信心，并體會(huì)到征服困難與不斷進(jìn)步的成就感。因此，我們采用由易到難、由淺入深的方法將遞歸算法的訓(xùn)練貫穿于整個(gè)數(shù)據(jù)結(jié)構(gòu)的教學(xué)過程中。

以嚴(yán)蔚敏的數(shù)據(jù)結(jié)構(gòu)教材[1]為例，從第六章“樹和二叉樹”開始，學(xué)生將陸續(xù)接觸到一系列復(fù)雜問題的遞歸算法，所以有必要在第六章教學(xué)之前就安排遞歸算法的講解與實(shí)驗(yàn)練習(xí)，通過比較簡單的遞歸問題使學(xué)生掌握使用遞歸思想分析問題的方法和遞歸算法的編寫模式，從而為后續(xù)復(fù)雜問題的遞歸算法教學(xué)鋪平道路，這部分實(shí)驗(yàn)稱為預(yù)備型實(shí)驗(yàn)。在后續(xù)教學(xué)的過程中，復(fù)雜問題遞歸算法的實(shí)驗(yàn)則根據(jù)相應(yīng)章節(jié)的教學(xué)進(jìn)度進(jìn)行安排，這部分實(shí)驗(yàn)分為設(shè)計(jì)型和驗(yàn)證型兩種。其中，驗(yàn)證型實(shí)驗(yàn)學(xué)生可以參考課本提供的算法，而設(shè)計(jì)型實(shí)驗(yàn)則完全靠自己進(jìn)行分析設(shè)計(jì)和算法實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)課程中遞歸相關(guān)內(nèi)容的實(shí)驗(yàn)安排如表2所示。

4 結(jié)束語

在以往的教學(xué)中，發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中算法的遞歸策略影響了學(xué)生對算法問題本身的理解，因此在數(shù)據(jù)結(jié)構(gòu)教學(xué)改革中增加了對遞歸思想和算法實(shí)現(xiàn)的講授與實(shí)驗(yàn)安排，講授部分包括遞歸算法的編寫方法、運(yùn)行機(jī)制與應(yīng)用場合分析，實(shí)驗(yàn)安排則將遞歸算法的訓(xùn)練貫穿于整個(gè)課程的教學(xué)過程中由易到難地展開。通過對教學(xué)改革后學(xué)生上課、實(shí)驗(yàn)及考試情況的觀察，學(xué)生在遞歸算法上犯錯(cuò)的比例比以往有很大程度的降低，遞歸算法不再是數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)中的絆腳石，學(xué)生對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)更加輕松和自信。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版） [M].北京：清華大學(xué)出版社，1997.

[2] 唐自立.數(shù)據(jù)結(jié)構(gòu)課程中遞歸算法教學(xué)探討[J]. 中國科技信息，2006（8）：290-291.

[3] 牛小飛， 李盛恩， 張冬梅，等.關(guān)于數(shù)據(jù)結(jié)構(gòu)中遞歸的教學(xué)探討[J]. 山東建筑大學(xué)學(xué)報(bào)，2010，25（6）：656-661.

[4] 王慧嬌.程序設(shè)計(jì)中遞歸函數(shù)教學(xué)問題探究[J]. 計(jì)算機(jī)教育，2010（16）：59-62.

[5] 郭韶升，張煒.數(shù)據(jù)結(jié)構(gòu)中遞歸算法的研究與實(shí)現(xiàn)[J].機(jī)械管理開發(fā)，2007（6）：90-91.

[6] 張永梅，馬禮.程序設(shè)計(jì)中的遞歸算法教學(xué)探討[J].華北工學(xué)院學(xué)報(bào)，2001（3）：38-39.