基于與遞推算法對(duì)比的遞歸教學(xué)方法思考

馬曉丹 王忠 范青剛 陳菁

摘 要 為了培養(yǎng)學(xué)生思考能力，計(jì)算思維能力，在算法的學(xué)習(xí)中運(yùn)用知識(shí)的正遷移。在課堂教學(xué)中進(jìn)行了同一問題不同算法解法的對(duì)比嘗試，有效提高了課堂教學(xué)效率。本文從兩種算法的程序結(jié)構(gòu)、終止條件、算法效率等方面系統(tǒng)進(jìn)行了比較，以結(jié)合課程內(nèi)容和學(xué)生的知識(shí)積累為基礎(chǔ)，循序漸進(jìn)積極引導(dǎo)學(xué)生思考，從而培養(yǎng)學(xué)生的學(xué)習(xí)興趣，發(fā)揮學(xué)生學(xué)習(xí)的主動(dòng)性，提高學(xué)生自主地發(fā)現(xiàn)問題、研究問題和解決問題的能力。

關(guān)鍵詞 遞推 遞歸 算法對(duì)比 正遷徙

Abstract In order to improve students' thinking ability， computing thinking ability， the positive transfer of knowledge is used in the learning of algorithms. In the classroom teaching， we tried to compare different algorithms and solutions of the same problem， which effectively improved the efficiency of classroom teaching. This paper systematically compares the algorithm structure， termination conditions， and algorithm efficiency of the two algorithms. Based on the combination of the curriculum content and the student's knowledge accumulation， actively guides students think step by step， cultivating students' learning interest and giving full play to their learning .Initiative to improve students' ability to discover， research and solve problems autonomously.

Keywords inductive; recursion; algorithm comparison; positive migration

1 問題提出

在程序基礎(chǔ)編程實(shí)現(xiàn)中，遞歸與遞推是兩種最為基礎(chǔ)和常見的算法。而在程序基礎(chǔ)的教學(xué)中，常常聽到學(xué)生說(shuō)計(jì)算機(jī)編程語(yǔ)言理解吃力，無(wú)法有效的對(duì)常用的這兩種算法進(jìn)行掌握、區(qū)分和應(yīng)用。而學(xué)生們感到程序基礎(chǔ)這門課難也主要是因?yàn)樯婕暗幕舅惴ㄋ枷氡容^抽象，對(duì)于剛接觸計(jì)算機(jī)的人來(lái)說(shuō)不易形象化的內(nèi)化理解。概念不清晰，知識(shí)點(diǎn)理解分離孤立，不好理解。

在教育心理學(xué)中的重要概念正遷移，是指一種學(xué)習(xí)對(duì)另一種學(xué)習(xí)起到積極的促進(jìn)作用。知識(shí)遷移的能力是指將所學(xué)知識(shí)應(yīng)用到其它新的情景下，并解決新問題時(shí)所體現(xiàn)出的一種素質(zhì)和能力，包含對(duì)新情境的感知和處理能力、舊知識(shí)與新情境的鏈按能力、對(duì)新問題的認(rèn)知和解決能力等層次。形成知識(shí)的有效的遷移能力可以避免對(duì)知識(shí)的死記硬背，實(shí)現(xiàn)知識(shí)點(diǎn)之間的貫通理解和轉(zhuǎn)換，有利于認(rèn)識(shí)事件的本質(zhì)和規(guī)律，構(gòu)建知識(shí)結(jié)構(gòu)網(wǎng)絡(luò)，提高解決問題的靈活性和有效性。正遷移， 通常表現(xiàn)為：（1）一種學(xué)習(xí)使另一種學(xué)習(xí)具有了良好的心理準(zhǔn)備狀態(tài)、活動(dòng)所需的時(shí)間或練習(xí)次數(shù)減少。（2）使另一種學(xué)習(xí)的深度增加、單位時(shí)間內(nèi)的學(xué)習(xí)量增加。（3）已經(jīng)具有的知識(shí)經(jīng)驗(yàn)使學(xué)習(xí)者順利地解決了面臨的問題等情況。[1]

在遞歸函數(shù)的教學(xué)中可以采用從數(shù)學(xué)歸納法到函數(shù)遞歸的思路，并對(duì)同一問題進(jìn)行函數(shù)封裝遞推算法到遞歸解法，在執(zhí)行中對(duì)比兩種算法的異同優(yōu)缺點(diǎn)的方法，有效進(jìn)行遞歸知識(shí)點(diǎn)的掌握和學(xué)習(xí)。

2 基于與遞推算法對(duì)比的遞歸教學(xué)設(shè)計(jì)

2.1 基于遞推算法的函數(shù)定義

在循環(huán)和函數(shù)概念的基礎(chǔ)上，讓學(xué)生編寫一個(gè)函數(shù)，求第n項(xiàng)斐波那契數(shù)列。目的一是鞏固和加強(qiáng)對(duì)循環(huán)遞推算法的理解，二是鞏固加強(qiáng)對(duì)函數(shù)定義的鞏固和應(yīng)用，采用循環(huán)遞推的方法解決的C語(yǔ)言代碼如下：

設(shè)置課堂討論環(huán)節(jié)，討論循環(huán)體內(nèi)的三個(gè)語(yǔ)句順序是否可以調(diào)換f3=f1+f2;f1=f2;f2=f3;得到的討論結(jié)果為遞推算法的本質(zhì)是根據(jù)已知數(shù)列的前面，使用遞推公式以此類推得到后面數(shù)值項(xiàng)。與數(shù)學(xué)中的遞推公式思想一致。拋出新的問題：題目同樣可以使是否可以用數(shù)學(xué)歸納法的方式解決？數(shù)學(xué)歸納法：用于證明斷言對(duì)所有自然數(shù)成立。

證明過(guò)程：

證明對(duì)于N=1成立

證明N>1時(shí)：假設(shè)對(duì)于N-1成立，那么對(duì)于N成立。

2.2 遞歸概念的引出

不同于數(shù)學(xué)歸納法的是，遞歸是計(jì)算機(jī)領(lǐng)域關(guān)于函數(shù)的特有概念，指的是函數(shù)對(duì)于自身的直接或者間接調(diào)用，就像Photoshop中的羅斯福效果：鏡子與鏡子對(duì)照出來(lái)的無(wú)限空間，也似盜夢(mèng)空間中表示的多層夢(mèng)境一樣。如此循環(huán)往復(fù)，但根據(jù)算法的有限性的特點(diǎn)，遞歸算法需要一個(gè)邊界條件，使得循環(huán)在某個(gè)條件滿足的時(shí)候，返回一個(gè)終值。這種方法通常能把一個(gè)大規(guī)模的復(fù)雜的問題轉(zhuǎn)化為一個(gè)與原問題相似的小規(guī)模問題來(lái)解決，以此來(lái)極大的提高代碼的可讀性并減少程序代碼量?？梢越o出斐波那契數(shù)列的遞歸形式表達(dá)式：

進(jìn)而寫出斐波那契數(shù)列的遞歸函數(shù)：

2.3 遞推與遞歸算法的對(duì)比

類似的對(duì)比例子還可以求n！、前n項(xiàng)和等，完成之后對(duì)比兩個(gè)代碼，讓學(xué)生討論和比較兩種算法的異同，同時(shí)執(zhí)行兩種算法的代碼，感受和對(duì)比執(zhí)行的效率?？偨Y(jié)如下：

遞推主要指遞推公式、遞推數(shù)列或遞推函數(shù)。一個(gè)數(shù)列的下一項(xiàng)由它前面幾項(xiàng)的一種運(yùn)算（或函數(shù)）構(gòu)成，如a[n]=a[n-1]+2、a[n]=a[n-1]+a[n-2]等。

遞歸主要指計(jì)算機(jī)上的遞歸函數(shù)，即會(huì)調(diào)用自己的一段函數(shù)代碼。

遞歸與迭代都是以控制結(jié)構(gòu)為基礎(chǔ)的：迭代直接在代碼形式上使用了循環(huán)結(jié)構(gòu)實(shí)現(xiàn)以此類推”，而遞歸直接使用了選擇結(jié)構(gòu)，進(jìn)行邊界條件的判斷和本函數(shù)的調(diào)用。

遞歸與迭代的本質(zhì)都是重復(fù)：迭代顯式使用重復(fù)結(jié)構(gòu)，而遞歸通過(guò)函數(shù)調(diào)用實(shí)現(xiàn)重復(fù)。

遞歸與迭代也都有終止條件的判斷：迭代在循環(huán)條件失敗時(shí)停止循環(huán)操作，遞歸在遇到邊界條件返回終值。[2]

總的來(lái)說(shuō)進(jìn)行程序設(shè)計(jì)時(shí)，遞歸算法的最大優(yōu)點(diǎn)是程序結(jié)構(gòu)清晰，可讀性強(qiáng)，當(dāng)我們把問題寫成遞歸形式的數(shù)學(xué)的表達(dá)式之后，與代碼有著極高的相似度。因此在實(shí)際使用中是一種常用的算法設(shè)計(jì)，尤其是在許多現(xiàn)實(shí)復(fù)雜的問題中，想要找到從初始條件開始一一推出所需結(jié)果的過(guò)程很難的時(shí)候，使用遞歸算法實(shí)現(xiàn)問題解決要簡(jiǎn)單的多。而隨之而來(lái)的缺點(diǎn)便是，遞歸算法在不同的調(diào)用階段會(huì)重復(fù)執(zhí)行同一個(gè)函數(shù)的計(jì)算，算法復(fù)雜度是指數(shù)級(jí)的，并且每一次的函數(shù)調(diào)用都要棧來(lái)實(shí)現(xiàn)不同調(diào)用階段的數(shù)據(jù)保存，頻繁的出棧和入棧使的空間消耗也是極大的。當(dāng)問題規(guī)模稍微大一些的時(shí)候，遞歸深度甚至超出可接受限度，（在Python中遞歸的嵌套深度不能超過(guò)998，當(dāng)調(diào)用棧超過(guò)998層就會(huì)報(bào)錯(cuò)）。

而同樣的問題對(duì)于設(shè)計(jì)良好的非遞歸算法的執(zhí)行效率就高得多，因此在問題解決之后也應(yīng)激勵(lì)學(xué)生進(jìn)一步的鉆研和討論如何將遞歸算法進(jìn)行非遞歸化以進(jìn)一步的優(yōu)化算法設(shè)計(jì)，提高代碼質(zhì)量。

2.4 遞歸算法的應(yīng)用擴(kuò)展

歸納總結(jié)可知遞歸算法是由遞歸出口和遞歸轉(zhuǎn)移函數(shù)構(gòu)成的（類似于動(dòng)態(tài)規(guī)劃中的狀態(tài)轉(zhuǎn)移方程）。一般遞歸算法框架為：

返回值函數(shù)名（形參列表）{ if （出口條件） return 返回值else { 根據(jù)狀態(tài)轉(zhuǎn)移方程遞歸調(diào)用自身return 返回值}怎么判斷問題可以使用遞歸來(lái)解決的？

問題可用遞歸來(lái)解決需具備的條件：子問題需與原問題為同樣的事，且規(guī)模更小;程序停止條件。并以經(jīng)典的漢諾塔問題和其他問題作為練習(xí)，鞏固對(duì)遞歸算法的理解和應(yīng)用。

3 結(jié)束語(yǔ)

在教學(xué)過(guò)程中，很多學(xué)生不能實(shí)現(xiàn)從數(shù)學(xué)思維到計(jì)算思維進(jìn)行轉(zhuǎn)換，遞推到遞歸的思維轉(zhuǎn)換的困難，因此在計(jì)算機(jī)程序設(shè)計(jì)和求解過(guò)程中面對(duì)類似實(shí)際問題描述的時(shí)候沒有思緒，無(wú)從下手，概念混淆，胡編亂造。這提示我們解決程序邏輯思維混亂的方法之一便是在平時(shí)的程序設(shè)計(jì)學(xué)習(xí)中以熟悉的數(shù)學(xué)知識(shí)概念為基礎(chǔ)，理清思緒。促進(jìn)知識(shí)正遷移，弱化或者克服知識(shí)負(fù)遷移。并且通過(guò)兩種算法的多方面對(duì)比加深學(xué)生對(duì)不同算法的理解和認(rèn)識(shí)，通過(guò)同時(shí)運(yùn)行兩個(gè)程序感受運(yùn)行時(shí)間的差異，激發(fā)學(xué)生對(duì)算法評(píng)價(jià)指標(biāo)的理解和重視，獲得良好的教學(xué)效果。

參考文獻(xiàn)

[1] 皮連生.學(xué)與教的心理學(xué)（第四版）.上海：華東師范大學(xué)出版社，2006.

[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1997.12：141.