高中《算法與程序設計》中的遞歸算法

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

一、明確教學目標

新課標指出：“算法部分旨在使學生進一步體驗算法思想，了解算法在解決問題過程中的地位和作用，并能從簡單問題出發，設計解決問題的算法。”遞歸算法的教學目標是學會用遞歸算法的思想分析問題。為了實現該目標，很多教師從遞歸函數代碼的理解出發帶領學生學習遞歸算法，而代碼的反復調用很容易給學生理解造成困難。筆者認為指導學生利用遞歸思想來分析問題是最重要的，理解了遞歸思想以后，代碼的編寫就變得相對容易了。

二、學生知識準備

所有的知識都不是空中樓閣，必須有一定的前期知識準備。學生開始學習遞歸算法前應該已經熟練掌握了順序結構、分支結構、循環結構，對程序設計語言有了一定的了解，能解決一些有一定難度的程序，有一定的分析問題的能力。而且，學生應該已經掌握了自定義函數，包括函數名、函數參數、函數參數之間的傳遞等知識。

三、理解遞歸過程

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

四、把握分析思路

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

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

這是一個典型的雙分支選擇結構語句，可以用IF語句來實現。

五、結合分析完成代碼

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

六、適時鞏固知識

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

然后，學生可以用斐波那契數列來進行練習。之所以用斐波那契數列來練習，是因為這個數列學生能很快找到規律，但又因為有兩處調用，有一定的難度提高。

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

七、適當提高應用

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

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

參考文獻：

[1]算法與程序設計.教育科學出版社.

[2]數據結構與算法.天津大學出版社.