周世杰

算法思維是計算思維的一個方面，而在計算機(jī)科學(xué)中，基于遞歸和迭代的思維方式在算法和程序設(shè)計中廣泛應(yīng)用，是算法思維的重要構(gòu)成部分。因此，信息技術(shù)學(xué)科教師在基礎(chǔ)課教學(xué)中辨析遞歸與迭代算法，將其作為發(fā)展學(xué)生計算思維的一項內(nèi)容，值得探索和實(shí)踐。

遞歸算法與迭代算法概述

無論是使用計算機(jī)還是日常解決問題，人們往往會碰到這樣一些情況：一個問題剛開始難以解決，但可以將其簡化后再嘗試解決;如果這樣解決問題的過程可以重復(fù)進(jìn)行，待解決的問題最終會變得容易處理。在算法和程序設(shè)計中，這樣的過程引出了兩種不同的方法：遞歸和迭代。

遞歸算法蘊(yùn)含著計算機(jī)學(xué)科的一些基本思想方法，它能為某些問題提供簡便的解決方案。遞歸算法是指一種方法被直接或間接地調(diào)用“自身”的過程。其基本思想如下：先將一個復(fù)雜的問題轉(zhuǎn)化為規(guī)?？s小了的類似子問題，設(shè)計出針對此子問題的解決方法，然后再次使用這樣的方式，直到縮小的問題變?yōu)橹庇^的可以解決的問題。例如，計算機(jī)算法中的“對分查找”問題可以采用遞歸算法這樣設(shè)計：在一個確定的已經(jīng)排好序的數(shù)組中，將“查找鍵”和“數(shù)組中點(diǎn)位置元素”不斷地進(jìn)行對比，根據(jù)對比結(jié)果，每次縮小一半的查找范圍，反復(fù)進(jìn)行，最終問題變?yōu)椴檎曳秶挥幸粋€數(shù)組元素，此時只要讓查找鍵和這最后一個數(shù)組元素比較，查找結(jié)果就很容易得出。

迭代本是數(shù)學(xué)中的一個重要方法，只是隨著計算機(jī)科學(xué)的快速發(fā)展，借用計算機(jī)運(yùn)算速度快等特點(diǎn)，迭代思想逐步演化為迭代算法。其基本思想如下：讓計算機(jī)對一定步驟（或一組指令）進(jìn)行重復(fù)操作，在每一次執(zhí)行這些步驟后，都能用變量的舊值（初值）計算出一個新值，通過新值的逐漸變化，達(dá)到（或逼近）最終結(jié)果的目的。例如，計算機(jī)算法和程序設(shè)計中的累加求和問題，通過設(shè)置一個變量（累加器），在循環(huán)結(jié)構(gòu)中，每次執(zhí)行都讓一個“數(shù)據(jù)”累加到這個變量中，通過控制循環(huán)次數(shù)，可以達(dá)到最終所需要的結(jié)果。

遞歸算法與迭代算法在算法和程序設(shè)計中應(yīng)用非常廣泛，因此也可以認(rèn)為是計算思維的重要內(nèi)容，但對于高中學(xué)生來說，一開始往往難以理解。在教學(xué)實(shí)踐中，筆者認(rèn)為可以通過具體的案例入手，用案例教學(xué)法，通過對比分析來促進(jìn)學(xué)生的理解。

一個算法實(shí)例

斐波那契數(shù)列（Fiboncci Sequence），又被稱為黃金分割數(shù)列，是指這樣一個數(shù)列：1、1、2、3、5、8、13、21……（即后一個數(shù)字是前兩個數(shù)字之和）。在數(shù)學(xué)中，該數(shù)列直接被以遞歸的形式定義：f（1）=1，f（2）=1，f（n）=f（n-1）+f（n-2） （n>2，n∈N）。在教學(xué)實(shí)踐中，筆者發(fā)現(xiàn)很多一線教師都會用“斐波那契數(shù)列”來作為教學(xué)實(shí)例，通過求解該數(shù)列第n項的問題設(shè)計算法。下面以求“斐波那契數(shù)列的第20項數(shù)值”為例，分別用遞歸和迭代算法表示。

1.用遞歸算法實(shí)現(xiàn)

遞歸算法是反復(fù)調(diào)用“自身”的過程，因此我們可以先定義一個函數(shù)[如f（n）]，然后在算法執(zhí)行中反復(fù)調(diào)用這個函數(shù)?；赩B語言，實(shí)現(xiàn)過程如圖1所示。

當(dāng)然，用遞歸的方式解決該問題，也可以不定義函數(shù)，而采用數(shù)組變量的方式實(shí)現(xiàn)，程序代碼如圖2所示。

以上兩種方式，其實(shí)質(zhì)是一樣的，都是根據(jù)該數(shù)列的數(shù)學(xué)定義，從第三項開始，對前兩項求和的反復(fù)使用。

2.用迭代算法實(shí)現(xiàn)

雖然斐波那契數(shù)列的數(shù)學(xué)定義是采用遞歸的形式，但用迭代算法一樣能夠解決，解決方案是先定義三個變量（如f1、f2、f3），然后對變量進(jìn)行更新賦值，同時利用循環(huán)控制執(zhí)行過程?；赩B語言，采用迭代算法解決這個問題的程序代碼如圖3所示。

當(dāng)然，針對這個問題，也可以只采用兩個變量實(shí)現(xiàn)，只需將“圖3”循環(huán)體內(nèi)代碼換為“f1=f1+f2：f2=f1-f2”，同時將輸出的內(nèi)容換為“Str（f1）”。

3.遞歸與迭代算法的簡單對比

就“求斐波那契數(shù)列的第20項數(shù)值”問題而言，由以上分析我們可以看到，用遞歸算法和迭代算法都能實(shí)現(xiàn)，但從算法執(zhí)行效率方面考慮，二者還是存在一定的差別的。

從“圖1”解決該問題的描述來說，在程序主語句中，對于n>3，每調(diào)用一次函數(shù)f，其實(shí)都會引起兩次該函數(shù)的調(diào)用。因此，如果求解的項數(shù)值比較大，調(diào)用函數(shù)f的總次數(shù)按指數(shù)增長，如此例中求第20項，函數(shù)f被調(diào)用次數(shù)近百萬次，顯然這樣的一個程序是不太實(shí)用的。而“圖3”中采用迭代算法實(shí)現(xiàn)該問題，就避免了同一值的重復(fù)計算問題，循環(huán)體內(nèi)只是執(zhí)行了54[（（20-3）+1）*3]次的賦值運(yùn)算，顯然效率更高。當(dāng)用計算機(jī)解決一個問題時，一般存在多種不同的方法。對于較小的問題，只要管用，方法不同并沒有什么關(guān)系。但對于大型問題或者需要解決大量小型問題的集合，我們就需要考慮算法的效率問題了。

在解決實(shí)際問題時，遞歸算法和迭代算法之間可以轉(zhuǎn)換，但它們的計算機(jī)執(zhí)行效率也并不是都和上例一樣——迭代優(yōu)于遞歸，但要具體問題具體分析。例如，另一個經(jīng)典算法案例“漢諾塔問題”，其遞歸算法中有兩處遞歸調(diào)用，并且其中一處的調(diào)用語句后面還有其他的非遞歸調(diào)用語句，要把這樣的問題用迭代的方式實(shí)現(xiàn)，相對比較復(fù)雜，并且它們并不會明顯提高程序的執(zhí)行效率，反而會使程序“不易讀”。

遞歸和迭代在算法和程序設(shè)計中作為特別有用的工具，可以幫助我們解決一些表面看起來非常復(fù)雜的問題。在教學(xué)實(shí)踐中，通過選擇合適的實(shí)例，并分析設(shè)計算法最終實(shí)現(xiàn)，可以幫助學(xué)生更好地理解其基本思想，培養(yǎng)算法思維。同時，在分析中如果對比算法執(zhí)行效率的問題，其實(shí)也是算法不斷優(yōu)化思想的體現(xiàn)，這些都是發(fā)展學(xué)生計算思維的要義所在。

從計算思維的角度看遞歸和迭代

計算思維涉及一些必要的思維技能，包括抽象和分解、遞歸思維、問題減少和轉(zhuǎn)換、錯誤預(yù)防和保護(hù)以及啟發(fā)式推理等，這些都是解決復(fù)雜問題所必需的。無論是日常生活還是在程序設(shè)計中，計算思維和程序設(shè)計應(yīng)該被看作獨(dú)立但兼容的認(rèn)知工具，它們都擴(kuò)展了問題解決的方式。遞歸和迭代作為計算思維的構(gòu)成內(nèi)容，同樣如此。作為算法，它們在程序設(shè)計中廣泛存在。其實(shí)從算法先于并且獨(dú)立于程序設(shè)計的角度，遞歸和迭代作為一種思維方式，普遍存在于我們解決問題之中。從計算思維的視角，在實(shí)現(xiàn)解決問題的過程中，它們具有以下特性。

1.問題分解

在NRC計算思維教學(xué)研討會報告中，Tinker曾說過：“計算思維的核心是將大的問題分解成很小的問題直到小的問題能夠自動化解決的思維過程?！边f歸和迭代可以說最好地反映了這樣的思想。在遞歸中，我們常說是調(diào)用“自身”的過程，這里的“自身”兩字往往是加了引號的，事實(shí)上，遞歸算法中的定義從來不是按某一事物本身來定義的，而是以比自身簡單一些的說法來定義。通過反復(fù)調(diào)用簡單的來實(shí)現(xiàn)復(fù)雜的功能，這里的簡單“自身”，其實(shí)就是對問題的分解。同樣，“迭”是屢次和反復(fù)，“代”就是替換，簡單來說，迭代就是反復(fù)替換的意思。事實(shí)上，在進(jìn)入替換之前，有一個“初始化”的過程，這個過程是根據(jù)問題本身的特點(diǎn)，找到簡單的已知的部分（如數(shù)列的初項等），在反復(fù)替換中達(dá)到解決問題的目的。像遞歸和迭代這種將一個復(fù)雜問題先簡單化處理的思想方式，很好地體現(xiàn)了計算思維的問題分解的特點(diǎn)。

2.問題構(gòu)造

在遞歸算法設(shè)計中，很重要的一點(diǎn)就是遞歸的逐層深入后必須有一個結(jié)束遞歸的條件或邊界，以逐層返回獲得結(jié)果。而在迭代算法中，實(shí)現(xiàn)反復(fù)替換的是循環(huán)結(jié)構(gòu)控制，它由以下三部分組成：①初始化：建立初始狀態(tài)，這一初始狀態(tài)會沿著終止條件變化;②測試：比較當(dāng)前狀態(tài)和終止?fàn)顟B(tài)，如果兩者相等，就結(jié)束循環(huán);③修改：向著終止條件的方向改變狀態(tài)。也就是說，無論是遞歸還是迭代的使用，都是有終止的，問題簡化到一定程度，一定是可以解決的，其實(shí)這體現(xiàn)了解決問題的構(gòu)造性特點(diǎn)，這也是計算思維的特征之一。

3.形式化表達(dá)

周以真認(rèn)為：計算思維的本質(zhì)是抽象和自動化。也可以這樣說，計算思維中的抽象是為了實(shí)現(xiàn)自動化而做的兩種抽象：一是過程抽象，即將解決問題的過程用形式化表達(dá);二是對象抽象，即用數(shù)據(jù)（變量）來表示對象。實(shí)現(xiàn)迭代算法的循環(huán)控制和實(shí)現(xiàn)遞歸算法的函數(shù)（過程）調(diào)用，都是簡潔而漂亮的形式化方式，它們在程序設(shè)計中已經(jīng)存在標(biāo)準(zhǔn)的模型，可以方便地將復(fù)雜問題的解決過程進(jìn)行形式化描述。形式化表達(dá)，既是計算機(jī)程序設(shè)計中對算法的要求，其實(shí)也是人們在解決實(shí)際問題過程中思維可視化的要求，所以也是計算思維的重要特征。

計算思維反映了計算機(jī)學(xué)科的核心方法和本質(zhì)，遞歸和迭代算法很好地反映了計算思維的特征。因此，在信息技術(shù)學(xué)科教學(xué)中，應(yīng)該對學(xué)生進(jìn)行遞歸和迭代算法的訓(xùn)練，從而促進(jìn)學(xué)生計算思維的發(fā)展。

結(jié)語

很多研究者提出，計算思維的教育不能僅僅停留在利用計算機(jī)解決問題上，而應(yīng)該通過問題解決方法的實(shí)踐來理解人與計算機(jī)的關(guān)系。但我們也應(yīng)該看到，計算思維是建立在計算機(jī)科學(xué)和計算機(jī)應(yīng)用層面之上的概念，如果脫離信息技術(shù)課程的具體內(nèi)容，單純討論計算思維的培養(yǎng)是很困難的。因此，我們應(yīng)該根據(jù)不同學(xué)段學(xué)生的心智特征，針對性地梳理反映計算思維核心特征的教育內(nèi)容，將計算思維的培養(yǎng)整合到這些內(nèi)容的具體教學(xué)活動之中。