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

馬曉丹 王忠 范青剛 陳菁

摘 要 為了培養學生思考能力，計算思維能力，在算法的學習中運用知識的正遷移。在課堂教學中進行了同一問題不同算法解法的對比嘗試，有效提高了課堂教學效率。本文從兩種算法的程序結構、終止條件、算法效率等方面系統進行了比較，以結合課程內容和學生的知識積累為基礎，循序漸進積極引導學生思考，從而培養學生的學習興趣，發揮學生學習的主動性，提高學生自主地發現問題、研究問題和解決問題的能力。

關鍵詞 遞推 遞歸 算法對比 正遷徙

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 問題提出

在程序基礎編程實現中，遞歸與遞推是兩種最為基礎和常見的算法。而在程序基礎的教學中，常常聽到學生說計算機編程語言理解吃力，無法有效的對常用的這兩種算法進行掌握、區分和應用。而學生們感到程序基礎這門課難也主要是因為涉及的基本算法思想比較抽象，對于剛接觸計算機的人來說不易形象化的內化理解。概念不清晰，知識點理解分離孤立，不好理解。

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

在遞歸函數的教學中可以采用從數學歸納法到函數遞歸的思路，并對同一問題進行函數封裝遞推算法到遞歸解法，在執行中對比兩種算法的異同優缺點的方法，有效進行遞歸知識點的掌握和學習。

2 基于與遞推算法對比的遞歸教學設計

2.1 基于遞推算法的函數定義

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

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

證明過程：

證明對于N=1成立

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

2.2 遞歸概念的引出

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

進而寫出斐波那契數列的遞歸函數：

2.3 遞推與遞歸算法的對比

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

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

遞歸主要指計算機上的遞歸函數，即會調用自己的一段函數代碼。

遞歸與迭代都是以控制結構為基礎的：迭代直接在代碼形式上使用了循環結構實現以此類推”，而遞歸直接使用了選擇結構，進行邊界條件的判斷和本函數的調用。

遞歸與迭代的本質都是重復：迭代顯式使用重復結構，而遞歸通過函數調用實現重復。

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

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

而同樣的問題對于設計良好的非遞歸算法的執行效率就高得多，因此在問題解決之后也應激勵學生進一步的鉆研和討論如何將遞歸算法進行非遞歸化以進一步的優化算法設計，提高代碼質量。

2.4 遞歸算法的應用擴展

歸納總結可知遞歸算法是由遞歸出口和遞歸轉移函數構成的（類似于動態規劃中的狀態轉移方程）。一般遞歸算法框架為：

返回值函數名（形參列表）{ if （出口條件） return 返回值else { 根據狀態轉移方程遞歸調用自身return 返回值}怎么判斷問題可以使用遞歸來解決的？

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

3 結束語

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

參考文獻

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

[2] 嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社，1997.12：141.