高中《算法與程序設(shè)計》中的遞歸算法

《算法與程序設(shè)計》是高中信息技術(shù)中重要的選修課之一。課程中涉及多種算法，比如：解析法、窮舉法、遞歸法等，其中遞歸法教師最難講解，學(xué)生也最不容易理解，很多師生對遞歸法望而卻步。在此，筆者結(jié)合自己的上課實踐與大家共同探討遞歸算法的教學(xué)。

一、明確教學(xué)目標(biāo)

新課標(biāo)指出：“算法部分旨在使學(xué)生進一步體驗算法思想，了解算法在解決問題過程中的地位和作用，并能從簡單問題出發(fā)，設(shè)計解決問題的算法?！边f歸算法的教學(xué)目標(biāo)是學(xué)會用遞歸算法的思想分析問題。為了實現(xiàn)該目標(biāo)，很多教師從遞歸函數(shù)代碼的理解出發(fā)帶領(lǐng)學(xué)生學(xué)習(xí)遞歸算法，而代碼的反復(fù)調(diào)用很容易給學(xué)生理解造成困難。筆者認(rèn)為指導(dǎo)學(xué)生利用遞歸思想來分析問題是最重要的，理解了遞歸思想以后，代碼的編寫就變得相對容易了。

二、學(xué)生知識準(zhǔn)備

所有的知識都不是空中樓閣，必須有一定的前期知識準(zhǔn)備。學(xué)生開始學(xué)習(xí)遞歸算法前應(yīng)該已經(jīng)熟練掌握了順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，對程序設(shè)計語言有了一定的了解，能解決一些有一定難度的程序，有一定的分析問題的能力。而且，學(xué)生應(yīng)該已經(jīng)掌握了自定義函數(shù)，包括函數(shù)名、函數(shù)參數(shù)、函數(shù)參數(shù)之間的傳遞等知識。

三、理解遞歸過程

興趣是最好的老師，越難理解的知識點越需要抓住學(xué)生的興趣點。對于遞歸算法的學(xué)習(xí)，我們可以先讓學(xué)生玩“漢諾塔”游戲。讓他們把塔盤從少到多慢慢增加，一邊玩一邊總結(jié)游戲攻略。通過老師的引導(dǎo)及動畫課件，學(xué)生應(yīng)該可以總結(jié)出“N個塔盤從A移動到C”的問題可以轉(zhuǎn)換成三個小問題：1.把N-1個塔盤從A移動到B；2.把第N個塔盤從A移動到C；3.把N-1個塔盤從B移動到C。教師只要適時地加以總結(jié)：“要想解決復(fù)雜問題，可以先把復(fù)雜問題轉(zhuǎn)化成簡單問題，把問題化解到最小，簡單問題解決了，那復(fù)雜問題也隨之解決。”并給出遞歸算法的概念：“直接或間接調(diào)用本身的算法”，以及遞歸算法的核心思想：遞歸分為兩個部分，一是遞推：大事化?。欢腔貧w：由小及大。當(dāng)然，教師也可以用“從前有座山”這個大家耳熟能詳?shù)墓适录右匝a充說明。

四、把握分析思路

在學(xué)生初步了解遞歸思想后，教師不應(yīng)急著進入代碼的講解，可以引導(dǎo)學(xué)生用遞歸思想來分析問題，從簡單到復(fù)雜，從具體到一般。可以從分析求5！開始，分析并總結(jié)出求N！的方法。在講解的過程中，教師可以借助黑板來板書分析思路。（如圖）

當(dāng)分析完5！的求解過程以后，教師可以讓學(xué)生分析討論出數(shù)學(xué)模型，其中包括：遞歸公式和邊界條件

這是一個典型的雙分支選擇結(jié)構(gòu)語句，可以用IF語句來實現(xiàn)。

五、結(jié)合分析完成代碼

在學(xué)生分析透徹以后，可以讓學(xué)生試著根據(jù)以往的函數(shù)知識完成代碼的編寫。這時可以利用“半成品”的形式，主要是讓學(xué)生填寫遞歸函數(shù)的主體（判斷語句）。然后，教師結(jié)合代碼再次說出遞歸的過程，學(xué)生的印象就很深刻了。這里學(xué)生可能會在兩個地方出錯：1.寫成fac（n）=fac（n-1）*n，解釋：函數(shù)的調(diào)用只能在表達式中，而等號是賦值語句，左邊只能是變量而不能是表達式。2.函數(shù)數(shù)據(jù)類型和接受返回值的變量數(shù)據(jù)類型不符，解釋：賦值語句等號左右兩邊數(shù)據(jù)類型必須相同。

六、適時鞏固知識

N！數(shù)學(xué)模型討論出以后，學(xué)生和教師一起經(jīng)歷了問題分析的過程。這時教師可以適當(dāng)小結(jié)遞歸概念、遞歸核心思想、遞歸邊界條件，來幫助學(xué)生鞏固所學(xué)知識。

然后，學(xué)生可以用斐波那契數(shù)列來進行練習(xí)。之所以用斐波那契數(shù)列來練習(xí)，是因為這個數(shù)列學(xué)生能很快找到規(guī)律，但又因為有兩處調(diào)用，有一定的難度提高。

當(dāng)然還是采用從具體到一般的方法，先在學(xué)案上分析第5項的數(shù)的求法，同時請兩位學(xué)生到黑板上來分析。再根據(jù)分析討論出遞歸公式和邊界條件（右圖為筆者上課時學(xué)生書寫的學(xué)案）。對這道題目的板書分析，以后在總結(jié)遞歸的缺點（重復(fù)調(diào)用）時也是可以利用的。

七、適當(dāng)提高應(yīng)用

在信息技術(shù)學(xué)科中，學(xué)生的能力存在較大差異。而遞歸算法又在理解上有一定的難度，自然學(xué)生達到學(xué)習(xí)目標(biāo)的情況也會有所差異。英國現(xiàn)代教育學(xué)家沛·西能在《教育原理》中說：“一切教育努力的根本目的應(yīng)該是幫助學(xué)生盡可能達到最高的個人發(fā)展。”所以，分層教學(xué)在信息技術(shù)中會經(jīng)常運用到。本課內(nèi)容可以采用難度稍高一點的遞歸題目作為提高題。筆者在教學(xué)的時候采用的是小球自由落體作為分層教學(xué)中的提高部分，同時采用小組討論的形式完成該題的分析。有些教師會讓學(xué)生編寫“漢諾塔”程序，筆者覺得難度太大，會把學(xué)生難住，造成學(xué)生產(chǎn)生排斥心理。

總之，遞歸法的教學(xué)重點必須落在“算法”上而不是“代碼”上。只要學(xué)生會用遞歸算法分析問題，那遞歸算法的代碼就很容易寫出來。而只有當(dāng)學(xué)生會用算法的思想分析問題，他們才能真正地體驗到算法的魅力，進而愛上《算法與程序設(shè)計》這門課。

參考文獻：

[1]算法與程序設(shè)計.教育科學(xué)出版社.

[2]數(shù)據(jù)結(jié)構(gòu)與算法.天津大學(xué)出版社.