《C語言程序設計》課程遞歸算法的教學設計

摘 要：遞歸算法是函數(shù)嵌套調(diào)用的一種特例，遞歸思想在程序設計中非常重要，遞歸思想的實質(zhì)就是把問題轉(zhuǎn)化為規(guī)模小的同類問題的子問題，這樣對原問題的研究就可轉(zhuǎn)移到子問題的研究，特別是當解決問題的條件不具備時，用遞歸算法去實現(xiàn)是非常有效的。通過對遞歸調(diào)用的學習，培養(yǎng)學生"自頂向下"、"逐步求精"的編程思想。

關鍵詞：遞歸算法；嵌套調(diào)用 ；編程思想

基于遞歸算法的編程思想是理論知識強且比較抽象的教學內(nèi)容，本次課主要運用任務驅(qū)動式教學模式和情境教學法，精心挖掘了一些生動、恰當?shù)睦?，讓學生更容易理解，利用游戲和視頻等圖文聲像并茂的傳播方式，增強了感染力，激發(fā)了學生的學習興趣。

一、新課引入（通過角色扮演，情景再現(xiàn)，提升學生的學習興趣）

引例：有4個人坐在一起，問第4個人歲數(shù)，他說比第3個人大2歲。問第3個人，又說比第2個人大2歲。問第2個人，說比第1個人大2歲。最后問第1人，他說是10歲。請問第5人到底多大？（舉一個通俗的例子來說明遞歸的思想）

二、遞歸的定義及條件

1.遞歸的定義：在調(diào)用一個函數(shù)的過程中又出現(xiàn)直接或間接地調(diào)用該函數(shù)本身，稱為遞歸算法。

2.遞歸的兩個條件：

（1）需要解決的問題可以化為一個或多個子問題來求解，而這些子問題的求解方法與原來的問題完全相同，只是在數(shù)量上、規(guī)模上不同。（遞歸方程）

（2）必須有遞歸結束條件來終止遞歸。（遞歸的結束標志）

三、根據(jù)遞歸的條件判斷以下的例子是否屬于遞歸（用小組討論的方式）

從前有座上，山里有座廟，廟里有老和尚在給小和尚講故事，講的什么呢？從前有座上，山里有座廟，廟里有個老和尚在給小和尚講故事，講的什么呢？從前有座上，山里有座廟，廟里有個老和尚在給小和尚講故事，講的什么呢？……

四、遞歸的經(jīng)典案例

1.情境導入漢諾塔問題

（先了解背景知識，滿足學生的好奇心，增強學習的興趣）

相傳在印度的一座大寺廟里有一塊黃銅板上插著三根寶石針，印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的64個金盤， 不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金盤：一次只移動一個金盤，不管在哪根針上，小盤必須放在大盤上面。當所有的金盤都從梵天穿好的那根針上移動到另外一根針上時，世界就將在一聲霹靂中消滅，梵塔、廟宇和眾生都將同歸于盡。

2.體驗游戲

這就是漢諾塔，現(xiàn)在已經(jīng)演變成家喻戶曉的益智游戲。那我們就玩漢諾塔游戲吧，（事先用flash制作好的游戲）教師先演示三層的情況，然后學生自告奮勇的上來玩四層的情況。）

通過玩游戲得出結論：

3個金盤由一根針移動到另一根針上至少需要7次， 即23-1

那64個金盤由一根針移動到另一根針上至少需要？（啟發(fā)學生進行思考）

264-1次。264-1，這是一個天文數(shù)字，如果每秒鐘移動一次，需要5800億年。如果計算機每一微秒實現(xiàn)一次移動，也需要5.8億年。

3.遞歸的實現(xiàn)與執(zhí)行

對漢諾塔問題研究的焦點集中在如何以最少的步驟完成全部金盤由一根針搬動到另一根針上。解決這個問題需要運用遞歸的思想。

哪怎么分解呢？不著急，先看一個視頻，讓學生從中會得到啟發(fā)。

（看如何把大象裝進冰箱的視頻）

得到的啟發(fā)是：

大象裝進冰箱可以分成三步，把64個金盤從一根針移動到另一根針能不能分成三步？ （與學生形成共鳴）

（用Autoware制作的課件演示漢諾塔的搬動過程，看到了嗎？問題已經(jīng)解決了。）

五、遞歸算法的特點

遞歸算法的優(yōu)點在于把復雜問題簡單化，用遞歸分析有些復雜問題思路非常清晰，而且程序簡單明了，同時把許多復雜的工作交給系統(tǒng)去處理，減輕了用戶的負擔。缺點是在遞歸過程中有大量數(shù)據(jù)需要保存，增加了系統(tǒng)空間的開銷，同時不斷重復調(diào)用自己，也增加了系統(tǒng)時間的消耗。

作者簡介：

1.陳祥（1973-），男，廣西岑溪人，教授，研究方向：課程改革、軟件技術.

基金項目：廣西工業(yè)職業(yè)技術學院2017年度教育教學改革立項課題：“高職計算機應用專業(yè)學生創(chuàng)新創(chuàng)業(yè)能力的探索與實踐”（項目批準編號：桂工業(yè)院2017[56]）.