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

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

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

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

引例：有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）必須有遞歸結(jié)束條件來終止遞歸。（遞歸的結(jié)束標(biāo)志）

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

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

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

1.情境導(dǎo)入漢諾塔問題

（先了解背景知識，滿足學(xué)生的好奇心，增強(qiáng)學(xué)習(xí)的興趣）

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

2.體驗(yàn)游戲

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

通過玩游戲得出結(jié)論：

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

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

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

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

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

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

（看如何把大象裝進(jìn)冰箱的視頻）

得到的啟發(fā)是：

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

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

五、遞歸算法的特點(diǎn)

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

作者簡介：

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

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