趙倩倩

摘要：迭代法與遞歸法的比較在2020版教科版高中信息技術教材必修1第四單元“4.3 非數(shù)值計算”中的拓展知識與選擇性必修1中的“3.1 迭代與遞歸”中均有所涉及，很多學生難以透徹理解二者的關系，導致在解決實際問題時不能靈活應用。作者通過對典型案例的深入探究，使學生明確迭代法與遞歸法實現(xiàn)過程與執(zhí)行效率及應用方面的異同，在解決問題時能辨證地看待與應用，達到了深度學習的效果。

關鍵詞：深度學習；遞歸法；迭代法；比較

中圖分類號：G434? 文獻標識碼：A? 論文編號：1674-2117（2023）11-0052-04

程序設計課深度學習的困境

深度學習是指在真正理解一個知識點的基礎上，能夠在新問題情境下靈活遷移運用該知識點，快速找到解決思路和方法的一種學習。它以聯(lián)系和理解為主要特征，鼓勵學生積極地反思、探索，發(fā)展學生分析、應用、評鑒和創(chuàng)造等高階思維能力。[1]在當前高中程序設計與算法的課堂教學中，部分學生存在“聽講時都會，解決實際問題時卻不知從何下手”“編程解決問題時沒有考慮程序的運行時間”“沒有評價算法執(zhí)行效率的意識”等問題。出現(xiàn)這些問題的原因有兩方面：一方面是由于程序設計的核心知識——算法的學習是高階思維的形成，難度較高，學生沒有真正理解、理清知識的內(nèi)涵、外延及相近知識之間的關系，不能熟練應用。另一方面是缺乏深度的教學使學生體驗得不深刻、思考得不深入、理解得不透徹。針對問題及原因，筆者嘗試以教科版高中信息技術教材必修1第四單元“4.3 非數(shù)值計算”中的拓展知識與選擇性必修1中的“3.1 迭代與遞歸”中都涉及的相似算法——迭代法與遞歸法的比較為例，探討如何進行基于深度學習的程序設計教學實踐。

基于深度學習的程序設計教學實踐

迭代法與遞歸法在程序設計中應用廣泛，是排序、搜索、查找、分治等經(jīng)典算法的基礎，但對高中生來說，剛開始學習時往往難以理解二者的異同。因此，在教學實踐中，教師應明確促進深度學習的教學目標，注重引導學生的高階思維投入，并從具體的案例開始，探究分別使用迭代法與遞歸法解決同一問題，使學生深入理解兩種算法的執(zhí)行過程與使用方法；通過對時間與空間消耗的分析來比較兩種算法的執(zhí)行效率，在此基礎上觸發(fā)學生深度思維，辯證地看待與使用算法解決實際問題。

1.尋找最近發(fā)展區(qū)，促進深度學習的開啟

教師提出問題：斐波那契數(shù)列是指像1、1、2、3、5、8、13、21……的數(shù)列，即后一項是前兩項之和，在數(shù)學中該數(shù)列定義為：f（1）=1，f（2）=1，f（n）=f（n-1）+f（n-2）（n＞2）。請說出數(shù)列的第20項數(shù)值。通過問題引入，學生在回顧數(shù)學知識的同時，體會當人工推算滿足不了需求時，就要借助編程計算。這里有兩種方法：一種是從已知值開始，通過遞推關系式一步一步地推出所求未知項的值，這種方法即迭代法。另一種是從所求未知項出發(fā)，通過調(diào)用函數(shù)，倒推至初始項，再代入初始項的值一步一步回推而求出未知項的值，這種方法即遞歸法。

在教學中，教師可以借助數(shù)學中經(jīng)典數(shù)列問題的定義，從學生的最近發(fā)展區(qū)入手，激發(fā)學生學習興趣并思考，由簡單的數(shù)學推算過渡到利用遞推關系式編程計算，由淺入深，使學生的思維由數(shù)學思維過渡到算法思維，促進深度學習的開啟。

2.解構算法核心概念，建立深度學習的聯(lián)接

深度學習的達成需觸發(fā)學生的深度思維，而深度思維首先應聚焦、解構概念的內(nèi)涵與外延。迭代法又稱輾轉法，是從初始值開始多次對過程進行重復，每一次迭代得到的結果都會被用來作為下一次迭代的初始值，以達到所求目標。遞歸法是指函數(shù)直接或間接調(diào)用自身的一種方法，其基本思想是把規(guī)模較大的問題層層轉化為規(guī)模較小的同類問題求解。

（1）從問題分解與構造的角度看迭代與遞歸

迭代法和遞歸法都是將大的問題分解成很小的問題直到小的問題能夠解決的方法。迭代法是從已知開始，即f（1）與f（2），通過循環(huán)結構實現(xiàn)反復替換，在反復替換中達到解決問題的目的，它有三個構造過程：①確定迭代變量的初始值；②建立遞推關系式；③迭代的結束條件，不能讓迭代無限重復。遞歸法則是從未知開始，通過反復調(diào)用函數(shù)直到遇到邊界f（1）與f（2），然后逐層返回獲得結果，它有兩個構造過程：

①遞推——通過逐層函數(shù)調(diào)用實現(xiàn)；②回歸——當獲得最簡單的情況即數(shù)列的初始項f（1）與f（2）后，逐步返回，依次得到問題的解。遞歸法函數(shù)調(diào)用過程如圖1所示。

（2）從形式化表達的角度看迭代與遞歸

實現(xiàn)迭代法的循環(huán)控制和實現(xiàn)遞歸算法的函數(shù)調(diào)用與選擇結構，都是形式化表達方式，它們在程序設計中已存在標準的模型，可以方便地將復雜問題的解決過程進行形式化描述。這里要注意f1，f2=f2，f1+f2是Python語言中的元組賦值方式，是對數(shù)列元素反復替換求解的形式化表示，同時創(chuàng)建兩個元組，然后將上一步的（f1，f1+f2）元組的值賦給當前的（f1，f2）元組，就實現(xiàn)了多個變量值的替換與更新。表1所示為對使用迭代法與遞歸法解決斐波那契數(shù)列問題的兩個方面進行的比較。

通過對迭代法與遞歸法核心概念的解構，引導學生對知識進行歸納與整理，促進學生理解并熟練掌握兩種算法在實現(xiàn)過程與形式化表達方面的異同，從而建立深度學習的聯(lián)接。

3.分析算法的執(zhí)行效率，促進深度理解

教師可以對算法執(zhí)行過程層層設疑，使教學目標更為具體化，進而為實現(xiàn)深度學習的目標提供可能。教師先請學生思考在使用迭代法與遞歸法分別計算fib（7）時，fib（3）計算了幾次。學生觀察程序發(fā)現(xiàn)在用迭代法計算時，循環(huán)體內(nèi)執(zhí)行了5次賦值運算，運行時間只隨循環(huán)次數(shù)的增加而增加，每次循環(huán)結束后變量的值將直接被替換更新，不占用額外空間。而在用遞歸法計算時，學生借助遞歸函數(shù)調(diào)用思維導圖（如上頁圖1），可以看到每個遞歸調(diào)用都觸發(fā)另外兩個遞歸調(diào)用，fib（3）被調(diào)用計算了5次。當n較大時就產(chǎn)生了大量的函數(shù)調(diào)用，而函數(shù)調(diào)用時參數(shù)壓到堆棧中，需為變量分配內(nèi)存空間，每深入一層都要占用一塊數(shù)據(jù)區(qū)域，產(chǎn)生許多額外的時間與空間消耗。最后，借助timeit模塊函數(shù)來統(tǒng)計程序運行所消耗的時間，隨著所求項數(shù)n的變化，兩種算法的時間消耗與空間占用對比如表2所示。

通過上述比較與分析，教師再引導學生進一步總結兩種算法的時間消耗與空間占用方面的特點，學會分析算法的執(zhí)行效率，層層深入，促進對兩種算法原理的深度理解，從而在面對實際問題時能合理地選用算法，辯證地看待與使用迭代法和遞歸法解決問題。

4.設置變構應用情境，鞏固深度學習的效果

深度學習往往意味著高難度的學習，根據(jù)認知負荷理論，深度學習知識本身的難度會增加學習的內(nèi)在認知負荷。[2]因此，教師可以通過針對性的鞏固練習，設置變構應用情境，將解決同一問題的不同算法代碼實現(xiàn)進行對比，同時對相同算法解決不同問題的代碼進行對比，做到算法與應用結合、代碼知識與應用結合，加強學生對應用這兩種算法編寫代碼解決實際問題的理解，從而突破難點。

以“求階乘問題”的兩種算法實現(xiàn)及比較為例，求正整數(shù)n的階乘。依據(jù)數(shù)學中對階乘的定義（一個正整數(shù)的階乘是所有小于及等于該數(shù)的正整數(shù)的積，0的階乘為1），引導學生對問題進行分解與構造，寫出n的階乘的遞推關系式n！=n*（n-1）*…*1。在用迭代法實現(xiàn)時需確定初始值與終止條件，使用循環(huán)結構進行數(shù)據(jù)的更新替換；在用遞歸法實現(xiàn)時需確定遞歸出口與定義遞歸調(diào)用函數(shù)。進一步設置進階變構應用，以“爬臺階問題”的兩種算法實現(xiàn)及比較為例，假設爬臺階有兩種方式，一種是一步邁1級臺階，另一種是一步邁2級臺階，請問爬n級臺階一共有多少種方式。提示學生從問題的分解與構造、形式化表達方面著手，分析問題的求解步驟。定義求解爬n級臺階的函數(shù)為num（n），如果第一步邁1級，那么剩下的n-1級臺階有num（n-1）種走法；如果第一步邁2級，那么剩下的n-2級臺階有num（n-2）種走法，提取算法的遞推關系式：num（n）=num（n-1）+num（n-2）。當n=1時，num（1）=1，當n=2時，有2種走法即num（2）=2，這兩個條件即為迭代法的初始值、遞歸法的邊界。這兩個問題的迭代法與遞歸法的Python實現(xiàn)代碼如上頁表3所示。

對比以上問題的兩種算法實現(xiàn)代碼，學生會發(fā)現(xiàn)迭代法與遞歸法都需要重復執(zhí)行某些代碼。迭代是重復執(zhí)行的過程，目的是逼近所求結果，通常使用計數(shù)器結束循環(huán)；遞歸是重復調(diào)用函數(shù)自身，當遇到滿足終止條件的情況時逐層返回。

再以必修1“4.3 非數(shù)值計算”中的拓展知識“漢諾塔游戲”為例，教師可以從數(shù)值計算過渡到非數(shù)值計算，發(fā)散學生思維。通過分析當n大于1的時候，可以考慮先將上面n-1個圓盤看作一個整體通過A移動到B上，再將A上的最后一個圓盤移動到C上，最后將B上的n-1個圓盤通過A移動到C上，對n-1個圓盤進行遞歸調(diào)用直到n=1時為遞歸出口，只需直接將A上的圓盤移動到C上即可。遞歸實現(xiàn)代碼如圖2所示，其中遞歸調(diào)用語句后還有非遞歸調(diào)用語句print（），如直接用迭代法解決將增加實現(xiàn)難度，導致代碼不易讀。

所以說，當一個問題相當復雜，難以根據(jù)當前所學知識應用迭代法實現(xiàn)時，遞歸實現(xiàn)的簡潔性便可以彌補它所帶來的運行時的開銷。同時，教師要引導學生在解決實際問題時具體問題具體分析，對于規(guī)模小的問題，可根據(jù)自己的偏好來選擇算法，但對于大型問題或特殊問題就需要綜合考慮算法的執(zhí)行效率與可讀性。這樣，通過知識整合、橫向與縱向對比，達到了提升批判性高階思維能力和解決復雜問題能力的教學目標，促進了學生對迭代法與遞歸法的靈活遷移運用，鞏固了深度學習的效果，激發(fā)了學生進一步探究與學習算法的興趣。

結語

通過對兩種算法執(zhí)行效率的比較，可以引導學生對程序執(zhí)行過程進行反思，這是算法不斷優(yōu)化思想的體現(xiàn)，并促使學生在反思與優(yōu)化中發(fā)現(xiàn)迭代法與遞歸法解決問題的特點，這樣既使學生全面掌握了知識，又發(fā)揮了學生的自主性，鍛煉了評價算法的能力。這些都是促進學生深度學習的途徑，也是發(fā)展學生計算思維的要義所在。

參考文獻：

[1]卜彩麗.深度學習視域下翻轉課堂教學理論與實踐研究[D].西安：陜西師范大學，2018.

[2]樂會進，蔡亮文.混合教學模式何以促進深度學習——基于翻轉課堂的研究[J].中國信息技術教育，2018（08）：143-147.

本文系2019年度湖北省教育信息技術研究與教育科學規(guī)劃重點課題“基于MOOCAP的大學先修課程高中實踐研究——以程序設計先修課為例”（課題編號：2019ZA57）研究成果之一。