小學(xué)編程社團(tuán)中遞歸“五步”教學(xué)法

浙江省金華師范附屬小學(xué) 潘洪波

遞歸是一種算法，無(wú)論是學(xué)習(xí)計(jì)算機(jī)語(yǔ)言，還是學(xué)習(xí)算法，遞歸一直伴隨其中；遞歸也是一種思維方式，許多復(fù)雜的問(wèn)題用遞歸的方式來(lái)思考就很容易解決。采用遞歸算法編寫(xiě)的程序直觀、易讀，理解遞歸概念，掌握遞歸本質(zhì)，學(xué)會(huì)用遞歸編寫(xiě)程序，對(duì)小學(xué)生以后的學(xué)習(xí)將有很大的幫助。筆者以六年級(jí)學(xué)生為教學(xué)對(duì)象，在編程社團(tuán)中經(jīng)過(guò)幾年的實(shí)踐，總結(jié)出“準(zhǔn)、明、歸、倒、煉”五步遞歸教學(xué)法。

一、準(zhǔn)

準(zhǔn)，即導(dǎo)入的案例要精準(zhǔn)，能讓學(xué)生形成正確的第一感性認(rèn)識(shí)。

小學(xué)生學(xué)習(xí)遞歸總是難以入門(mén)、難以掌握，為什么會(huì)這樣？常規(guī)課堂教學(xué)一般采用故事導(dǎo)入，如老和尚講故事——“從前有座山，山上有座廟，廟里有一個(gè)老和尚在給小和尚講‘從前有座山，山上有座廟，廟里有一個(gè)老和尚在給小和尚講……’”，或用“德羅斯特效應(yīng)”導(dǎo)入，比較經(jīng)典的就是一個(gè)人拿著一個(gè)相框，相框里他拿著相框……

用這類(lèi)故事導(dǎo)入生動(dòng)有趣，容易活躍課堂氣氛，但對(duì)理解遞歸的本質(zhì)是不利的。遞歸的本質(zhì)就是分而治之，通過(guò)“遞”將一個(gè)大型的、復(fù)雜的問(wèn)題層層分解為若干與原問(wèn)題性質(zhì)相同的、規(guī)模更小的子問(wèn)題來(lái)處理，當(dāng)規(guī)模小到一定程度時(shí)，可以直接得出它的解，然后利用“歸”,層層回歸、逐步向上求解就可以得到原問(wèn)題的解。用函數(shù)實(shí)現(xiàn)時(shí)，因?yàn)榻鉀Q大問(wèn)題的方法和解決小問(wèn)題的方法往往是同一種方法，所以就產(chǎn)生了直接或間接調(diào)用自身的情況。遞歸算法是一種“自己調(diào)用自己”“有去有回”的算法。

“老和尚講故事” “德羅斯特效應(yīng)”有的只是“自己調(diào)用自己”的重復(fù)，但并沒(méi)有分而治之的思想（將大問(wèn)題解決轉(zhuǎn)化成小的子問(wèn)題），也沒(méi)出現(xiàn)遞歸結(jié)束條件，更沒(méi)有“遞”和“歸”以及“有去有回”的過(guò)程。用這類(lèi)故事導(dǎo)入，容易讓學(xué)生形成一種錯(cuò)誤的認(rèn)識(shí):遞歸就是重復(fù),遞歸就是循環(huán)。

第一印象、第一感知很重要，如果一開(kāi)始就理解錯(cuò)了，以后就更難學(xué)了。有沒(méi)有更好的例子呢？筆者選用《小學(xué)生C++趣味編程》中“交作業(yè)啦”為課堂導(dǎo)入的例子。

這個(gè)例子中有分而治之的思想：求第1 個(gè)學(xué)生交的作業(yè)數(shù)，可以先求第2 個(gè)學(xué)生要交的作業(yè)數(shù)；求第2個(gè)學(xué)生交的作業(yè)數(shù)，可以先求第3 個(gè)學(xué)生要交的作業(yè)數(shù)……要解決的問(wèn)題性質(zhì)不變但規(guī)模越來(lái)越小。每個(gè)學(xué)生都是收作業(yè)，就是“自己調(diào)用自己”。前一個(gè)學(xué)生轉(zhuǎn)過(guò)去對(duì)后一個(gè)學(xué)生說(shuō)“交作業(yè)啦”，這就是“遞”的過(guò)程?！暗? 個(gè)是格萊爾，她是一組中的最后一個(gè)學(xué)生”，這就是遞歸結(jié)束條件，可以直接得出它的解。把自己的作業(yè)連同收到的作業(yè)交給前一個(gè)同學(xué)，這就是“歸”的過(guò)程。“交作業(yè)啦”完整地演繹了遞歸算法的“自己調(diào)用自己” “有去有回”的過(guò)程，能讓學(xué)生形成正確的第一感性認(rèn)識(shí)。

二、明

明，即讓學(xué)生明白遞歸的概念及遞歸程序的執(zhí)行過(guò)程。教學(xué)時(shí)可以先分析執(zhí)行過(guò)程再提出概念，這樣就能讓學(xué)生在動(dòng)態(tài)的過(guò)程中理解靜態(tài)的概念。

遞歸程序在執(zhí)行時(shí)分兩步：第一步是“遞歸前進(jìn)”；第二步是“遞歸返回”。要想讓學(xué)生明白這一過(guò)程，教師可以畫(huà)一畫(huà)遞歸執(zhí)行圖。（見(jiàn)圖1）

圖1 遞歸執(zhí)行圖

學(xué)生在繪制“遞”與“歸”的路徑中動(dòng)態(tài)地理解遞歸概念。程序執(zhí)行zuoye(1)時(shí)，要調(diào)用zuoye(2)；執(zhí)行zuoye(2)時(shí)，要調(diào)用zuoye(3)……執(zhí)行zuoye(6)時(shí)，要調(diào)用zuoye(7)，這就是“遞歸前進(jìn)”。zuoye(7)為1，求出zuoye(6)為2； zuoye(6)為2，求出zuoye(5)為3……最后求出zuoye(1)為7，這就是“遞歸返回”。

三、歸

歸，即根據(jù)遞歸執(zhí)行圖，找到邊界條件及邊界值，歸納出遞歸表達(dá)式。在歸納遞歸表達(dá)式時(shí)，先寫(xiě)出分步表達(dá)式，再歸納出綜合表達(dá)式，因?yàn)榉植奖磉_(dá)式會(huì)在題目中直接或間接地呈現(xiàn)，容易寫(xiě)出，而綜合表達(dá)式需要推理才能得出，難度大一些，在此要遵循先簡(jiǎn)單后復(fù)雜的原則。

分步表達(dá)式：

zuoye(1)=zuoye(2)+1

zuoye(2)=zuoye(3)+1

zuoye(3)=zuoye(4)+1

zuoye(4)=zuoye(5)+1

zuoye(5)=zuoye(6)+1

zuoye(6)=zuoye(7)+1

zuoye(7)= 1

綜合表達(dá)式：

這樣，根據(jù)遞歸表達(dá)式寫(xiě)出程序就容易多了。

在此過(guò)程中，教師要讓學(xué)生明白，遞歸表達(dá)式是解決問(wèn)題的通式，掌握歸納遞歸表達(dá)式的方法——可以先寫(xiě)出分步表達(dá)式，找出其中的規(guī)律，再寫(xiě)出綜合表達(dá)式。同時(shí)要讓學(xué)生明白，并不是所有的問(wèn)題都能用遞歸的方法來(lái)解決，用遞歸解決問(wèn)題時(shí)是有條件的：原問(wèn)題可轉(zhuǎn)化為規(guī)模更小的子問(wèn)題，子問(wèn)題和原問(wèn)題有相同的解決方法；問(wèn)題可以繼續(xù)轉(zhuǎn)化，轉(zhuǎn)化后問(wèn)題規(guī)模更小；在有限次轉(zhuǎn)化后，根據(jù)遞歸結(jié)束的條件（邊界條件）能得到最小子問(wèn)題的值（邊界值）。

四、倒

倒，即根據(jù)程序倒推出遞歸表達(dá)式，畫(huà)出遞歸執(zhí)行圖,并說(shuō)一說(shuō)程序的作用，進(jìn)行鞏固練習(xí)，只有鞏固后才能應(yīng)用。這個(gè)過(guò)程可以借助于閱讀程序?qū)懡Y(jié)果方式進(jìn)行由淺入深的訓(xùn)練。

可以先讓學(xué)生說(shuō)一說(shuō)、寫(xiě)一寫(xiě)上面這個(gè)程序遞歸表達(dá)式，在說(shuō)和寫(xiě)遞歸表達(dá)式時(shí)，要先綜合表達(dá)式后分步表達(dá)式（因?yàn)榇藭r(shí)綜合表達(dá)式、邊界條件和邊界值在程序中能找到，而分步表達(dá)式需要推理才能得出，所以寫(xiě)出綜合表達(dá)式比分步表達(dá)式容易），然后畫(huà)一畫(huà)遞歸執(zhí)行圖，交流“遞”與“歸”的具體執(zhí)行路徑，最后思考程序的功能。

同時(shí)也可以引導(dǎo)學(xué)生針對(duì)遞歸的問(wèn)題用遞推的方式來(lái)解,先找到最小問(wèn)題的解，然后逐步求稍大問(wèn)題的解，最后求出原問(wèn)題的解，為遞歸與遞推的轉(zhuǎn)化做鋪墊。

需要注意的是，入門(mén)階段遞歸函數(shù)參數(shù)的個(gè)數(shù)要少，建議用一個(gè)，不用兩個(gè)或多個(gè)，主程序調(diào)用遞歸函數(shù)實(shí)參數(shù)值要小，建議在5 以?xún)?nèi),這樣易于小學(xué)生分析、畫(huà)圖、理解，可以節(jié)約時(shí)間、提高學(xué)習(xí)效率。

五、煉

煉，即提煉出編寫(xiě)遞歸程序的方法,以實(shí)現(xiàn)學(xué)以致用。

這個(gè)過(guò)程以上機(jī)編程訓(xùn)練為主，訓(xùn)練時(shí)可分兩步走：第一步，根據(jù)已知邊界條件和邊界值、遞歸表達(dá)式直接寫(xiě)出程序；第二步，根據(jù)問(wèn)題描述，由學(xué)生自己找出邊界條件和邊界值，推導(dǎo)出遞歸表達(dá)式，然后編寫(xiě)程序。

所選的題目題意要淺顯，要讓學(xué)生很容易就能找到邊界條件和邊界值，歸納出遞歸表達(dá)式。學(xué)生不應(yīng)花大量的時(shí)間在數(shù)學(xué)分析上、花大量的精力在數(shù)學(xué)公式的推導(dǎo)上，應(yīng)把時(shí)間和精力放在“遞歸”本身上。題目只是載體，學(xué)生通過(guò)這個(gè)載體來(lái)學(xué)習(xí)、鞏固、提高、應(yīng)用遞歸算法。