從計(jì)算思維的視角辨析算法中的遞歸與迭代

周世杰

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

遞歸算法與迭代算法概述

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

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

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

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

一個(gè)算法實(shí)例

斐波那契數(shù)列（Fiboncci Sequence），又被稱為黃金分割數(shù)列，是指這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21……（即后一個(gè)數(shù)字是前兩個(gè)數(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)很多一線教師都會(huì)用“斐波那契數(shù)列”來作為教學(xué)實(shí)例，通過求解該數(shù)列第n項(xiàng)的問題設(shè)計(jì)算法。下面以求“斐波那契數(shù)列的第20項(xiàng)數(shù)值”為例，分別用遞歸和迭代算法表示。

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

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

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

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

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

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

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

3.遞歸與迭代算法的簡(jiǎn)單對(duì)比

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

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

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

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

從計(jì)算思維的角度看遞歸和迭代

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

1.問題分解

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

2.問題構(gòu)造

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

3.形式化表達(dá)

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

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

結(jié)語

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