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

馬曉丹 王忠 范青剛 陳菁

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

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

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ǔ)編程實現(xiàn)中，遞歸與遞推是兩種最為基礎(chǔ)和常見的算法。而在程序基礎(chǔ)的教學(xué)中，常常聽到學(xué)生說計算機(jī)編程語言理解吃力，無法有效的對常用的這兩種算法進(jìn)行掌握、區(qū)分和應(yīng)用。而學(xué)生們感到程序基礎(chǔ)這門課難也主要是因為涉及的基本算法思想比較抽象，對于剛接觸計算機(jī)的人來說不易形象化的內(nèi)化理解。概念不清晰，知識點理解分離孤立，不好理解。

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

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

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

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

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

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

證明過程：

證明對于N=1成立

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

2.2 遞歸概念的引出

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

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

2.3 遞推與遞歸算法的對比

類似的對比例子還可以求n！、前n項和等，完成之后對比兩個代碼，讓學(xué)生討論和比較兩種算法的異同，同時執(zhí)行兩種算法的代碼，感受和對比執(zhí)行的效率。總結(jié)如下：

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)

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

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