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

周世杰

算法思維是計算思維的一個方面，而在計算機科學中，基于遞歸和迭代的思維方式在算法和程序設計中廣泛應用，是算法思維的重要構成部分。因此，信息技術學科教師在基礎課教學中辨析遞歸與迭代算法，將其作為發展學生計算思維的一項內容，值得探索和實踐。

遞歸算法與迭代算法概述

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

遞歸算法蘊含著計算機學科的一些基本思想方法，它能為某些問題提供簡便的解決方案。遞歸算法是指一種方法被直接或間接地調用“自身”的過程。其基本思想如下：先將一個復雜的問題轉化為規模縮小了的類似子問題，設計出針對此子問題的解決方法，然后再次使用這樣的方式，直到縮小的問題變為直觀的可以解決的問題。例如，計算機算法中的“對分查找”問題可以采用遞歸算法這樣設計：在一個確定的已經排好序的數組中，將“查找鍵”和“數組中點位置元素”不斷地進行對比，根據對比結果，每次縮小一半的查找范圍，反復進行，最終問題變為查找范圍只有一個數組元素，此時只要讓查找鍵和這最后一個數組元素比較，查找結果就很容易得出。

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

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

一個算法實例

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

1.用遞歸算法實現

遞歸算法是反復調用“自身”的過程，因此我們可以先定義一個函數[如f（n）]，然后在算法執行中反復調用這個函數。基于VB語言，實現過程如圖1所示。

當然，用遞歸的方式解決該問題，也可以不定義函數，而采用數組變量的方式實現，程序代碼如圖2所示。

以上兩種方式，其實質是一樣的，都是根據該數列的數學定義，從第三項開始，對前兩項求和的反復使用。

2.用迭代算法實現

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

當然，針對這個問題，也可以只采用兩個變量實現，只需將“圖3”循環體內代碼換為“f1=f1+f2：f2=f1-f2”，同時將輸出的內容換為“Str（f1）”。

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

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

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

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

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

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

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

1.問題分解

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

2.問題構造

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

3.形式化表達

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

計算思維反映了計算機學科的核心方法和本質，遞歸和迭代算法很好地反映了計算思維的特征。因此，在信息技術學科教學中，應該對學生進行遞歸和迭代算法的訓練，從而促進學生計算思維的發展。

結語

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