余艷　劉燕麗

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

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

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2014）04-0784-04

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

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

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

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

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

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

2 遞歸算法及實現(xiàn)的教學要點

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

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

2.1 遞歸算法的編寫思路

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

例1：計算n階乘，其中n為非負整數(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é)點，結(jié)點的存儲結(jié)構(gòu)定義為

typedef struct Node{

int data；

struct Node *next；

}Node；

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

void RevPrint（Node *p）{

if （p）{

RevPrint（p→next）；

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

}

}

2.2 遞歸算法的實現(xiàn)機制

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

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

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

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

2.2.2 遞歸工作棧

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

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

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

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

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

3）遞歸工作棧示例

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

2.3 遞歸算法的使用場合

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻：

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

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

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

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

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

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