以計算思維為切入點的遞歸算法教學改革

朱君波+龔沛曾+楊志強

摘 要：程序設計課程是培養學生計算思維能力的重要課程，其中的遞歸算法設計體現了計算思維中問題分解、抽象和自動化的本質。文章提出以計算思維為切入點進行教學改革，圍繞計算思維的能力培養，重新整理遞歸教學內容，改革教學方法，變知識的教學為思維的訓練。

關鍵詞：計算思維；程序設計；遞歸算法；教學改革

文章編號：1672-5913（2017）07-0030-04

中圖分類號：G642

0 引 言

遞歸函數（過程）是在其定義中直接或間接調用自身的一種函數（過程）。通過設計遞歸函數（過程）來解決問題的算法就是遞歸算法。遞歸算法的設計思想是分治思想的典型代表，利用遞歸算法編寫的程序具有結構簡單清晰、可讀性強的特點。許多復雜的問題都可以通過遞歸算法來簡化，以簡單的形式得出結果。

2010年11月，陳國良院士在第六屆大學計算機課程報告論壇上，第一次正式提出將“計算思維能力培養”作為計算機基礎課程教學改革的切入點 [1]。隨后教育部高教司設立了以計算思維為切入點的大學計算機課程改革項目[2]。

在大學計算機的教學中，程序設計課程是培養學生計算思維能力的有效途徑[3]。遞歸是程序設計課程中固有的內容，也是教學難點。如何讓非計算機專業學生（尤其是非理工類的學生）理解遞歸、利用遞歸算法求解問題，是教學中面臨的新問題[4]。

1 傳統的遞歸教學

在傳統的遞歸教學中，教師往往將重點放在遞歸算法的解釋上，而教學方法則采用“介紹—舉例—演示”三步曲教學法。一般以求階乘的典型例子作為介紹，然后通過一些具有數學上很直觀的遞歸函數，如斐波那契數列作為舉例，最后演示經典的“漢諾塔”問題作為結束。

在這種教學方法中，教師僅針對問題解釋遞歸算法，學生從表面上看程序代碼只有寥寥數行，看似簡單，但遞歸如何執行，學生并不了解，覺得很懸乎；同時學生對現有的例子又感覺沒有實際應用價值。

在以計算思維為切入點的教學改革實施以來，我們認識到遞歸算法解決問題的重要性。傳統的遞歸教學在宏觀上沒有掌握遞歸的精髓——問題的分解、抽象和自動化；在微觀上沒有從遞歸的執行過程分析。學生學習時聽得云里霧里，更不要說讓學生自己設計一個遞歸函數（過程）去解決實際問題了；教師也僅僅完成了教學要求，以至于在學時壓縮的情況下這部分內容也自然而然地被刪除了。

2 遞歸教學的新認識

利用計算思維的方法設計遞歸，首先理解什么是遞歸現象？遞歸的核心思想是什么？如何理解遞歸的執行過程？如何利用計算思維的方法設計遞歸算法？

2.1 認識遞歸現象

首先從日常生活中遇到的遞歸現象開始。在圖1中，兩面鏡中產生一連串的“像中像”；也可以從大家熟悉的“老和尚給小和尚講故事”“阿凡提和國王下棋賞麥粒”等故事開始。通過這些常見遞歸現象的展示，讓學生對遞歸有個感性認識。

其次，通過展示遞歸數學公式，讓學生對遞歸函數的實現有所了解。這里可以引用學生熟悉的求n階乘公式：

并給出其對應的遞歸函數（程序代碼使用VB.NET編寫）：

Function f#（ByVal n% ）

If （ n < 2 ） Then

f=1

Else

f=n*f（n-1）

End If

End Function

2.2 遞歸核心思想

通過認識遞歸現象，引導學生理解遞歸的實質是“分而治之”“大問題分解為本質相同的小問題”的思想，如圖2所示。問題分解是計算思維的典型方法，也是遞歸算法的核心思想，應貫穿于分析和設計遞歸函數的始終。

2.3 遞歸的執行過程

遞推和回歸是遞歸執行過程的兩個基本要素。遞推是從大問題到小問題，等待小問題的答案，回歸是小問題返回給大問題答案。圖3以n階乘遞歸函數計算4階乘為例，示意遞歸的執行過程。

計算機在執行遞歸的過程中，遞推和回歸的過程是利用棧來實現的。棧是計算機中特殊的存儲區，主要功能是暫時存放數據和地址。棧的特點是先進后出，它有壓棧和彈出兩個基本操作。每一次的遞推過程實質是壓棧操作，將函數的參數、變量和返回地址等數據保存在棧中。每一次回歸的過程就是棧的彈出操作，將棧中保存的數據釋放。

2.4 利用計算思維的方法設計遞歸算法

設計遞歸算法的關鍵是要根據具體的問題，通過分解抽象出遞歸模式，再利用計算機本身的函數調用機制實現自動化。這種分解、抽象和自動化的方法正是計算思維的本質。

3 以遞歸模式為中心的遞歸算法設計

以遞歸模式為中心的遞歸算法設計分成3個步驟：問題分解、抽象和自動化。

3.1 問題分解

問題分解就是將大的、復雜的問題分解為本質相同的、規模較小的問題，當小問題解決，那么大問題也解決了。而規模較小的問題，因為本質上是和大問題相同的，可以用同樣的方法繼續分解為規模更小的子問題。這樣通過一系列的分解，最后分解到能直接給出結果的最小問題，然后再逐漸返回，最終大問題得以解決。

在問題分解中，需要注意兩點：一是分解后的小問題的規模要變小，例如n階乘的小問題是n-1的階乘，它的規模更小，而不是規模更大的n+1；二是問題小到一定程度時不能再小，直接得出結果，例如階乘，當n=1時不能再小了，得出結果是1。

3.2 抽 象

根據問題分解的結果，正確地將大問題和多個小問題之間的邏輯關系表達出來，變成遞歸模式。遞歸模式就是小問題與大問題之間的邏輯關系，即大問題是如何隨著小問題的解決而完成的？

這里有3種情況：第一種是邏輯或的關系，只要其中一個小問題解決，則大問題解決。例如，n階乘問題，分解成數字n和n-1的階乘，只要n-1階乘解決則n階乘解決。第二種是邏輯與的關系，多個小問題都要解決，但與小問題解決的先后順序無關，如斐波那契數列。第三種也是邏輯與的關系，但與多個小問題的解決順序是有關聯的，如數組排序問題。

3.3 自動化

得到了遞歸模式之后，根據程序設計語言，編寫相應的遞歸函數就能實現遞歸算法了。遞歸算法自動化的實現，本質是利用計算機本身的函數調用機制。計算機的函數調用機制就是函數調用棧，它的壓棧操作就是遞推，它的彈出操作就是回歸。

4 遞歸案例

設計合理的教學案例是保證良好教學的關鍵。一個成功的教學案例可以豐富課堂內容，活躍課堂氣氛，激發學生的積極性，促進教師與學生的互動。

在遞歸的教學過程中，教師常常覺得案例不夠豐富，這也是困擾教學的一個問題。其實遞歸的案例無處不在，只要細心去挖掘，程序設計中常見的算法都可以成為遞歸的案例。將這些算法按照數據類型進行簡單的歸類，即整數處理、字符串處理和數組處理等，同類的問題具有相似的問題分解方法和遞歸模式。

4.1 整數處理

整數處理類的常見問題有最大公約數、整數位數和數制轉換等。這類案例的遞歸算法設計過程如下：首先通過整除和取余，將被處理的整數分解成商和余數；其次建立被除數、商和余數的邏輯關系，抽象出遞歸模式；最后，通過函數定義，將遞歸模式編寫成遞歸算法。

我們以求整數m的位數為例，分析整數的遞歸算法設計。第一步，將被除數m除以10，分解成商（m＼10）和余數。商也是個整數也有位數，可以用同樣的方法繼續分解，當商為0，則m是1位數，是最小問題，不再分解。

第二步，抽象出遞歸模式。被除數m（大問題）和商m＼10（小問題）與余數（小問題）的邏輯關系是：m的位數等于商的位數+1，與余數無關。屬于第一種遞歸模式，只要得到商的位數（遞歸調用獲得），則被除數的位數也將獲得，得到如下遞歸模式：

第三步，根據遞歸模式編寫遞歸函數：

Function fig%（ByVal m%）

If m ＼ 10 = 0 Then

fig = 1

Else

fig = fig（m ＼ 10） + 1

End If

End Function

4.2 字符串處理

字符串類問題的分解一般如下：將一個字符串按照位置分成一個字母（第一個或最后一個）和去除一個字母后的子串。子串比原先的字符串個數少、規模小，而且它也可以用相同的方法繼續分解。當字符串的長度為0時，這是最小問題，不能再分解了。

例如，將字符串中的數字字符提取出來，組成新的數字子串。如字符串“d1d8ffd76yu9” 提取出數字字符串“18769”。

第一步，將字符串s分解成第一個字母（用c表示）和后面的子串（s1=mid（s，2））。當字符串長度為0時，這是最小問題，不能再分解。

第二步，抽象出遞歸模式，s的數字串就是c和s1的數字串的連接。屬于遞歸模式中的第二種情況，兩個子問題都要解決。c的數字子串就是判斷c是否為數字字符。s1的數字子串通過遞歸調用獲得。因此，得到如圖4所示的遞歸模式。

第三步，根據遞歸模式編寫遞歸函數代碼。程序代碼相對簡單，不再贅述。

4.3 數組處理

數組的處理一般是通過循環實現的，碰到復雜的操作，如排序，則要進行多重循環。在學生循環概念薄弱的情況下，多重循環將是學生的噩夢。

數組的分解方法和字符串有點類似：按照位置（下標）將數組分解成一個位置（第一個或最后一個）和其余位置的子數組。每次分解后會減少一個位置，規模越來越小；當數組下標上界為0（數組長度為1）時，不再分解。

例如，將數組a中的0～n個數進行按位置（下標）遞增排序，遞歸的排序過程名設為sort（a，n）。第一步，將數組a（n）分解成兩部分：0～n-1的子數組和第n個元素，如圖5所示。這樣將a（n）的排序就分解成了a（n-1）的排序和第n個位置數據的確定了。a（n-1）的排序可以用同樣的方法繼續分解，當n=0是最小問題。

第二步，按照前面的分解，整個排序就是兩個步驟：先是第n個位置數據的確定，然后是0～n-1的子數組排序（遞歸調用sort（a，n-1）實現），得到如圖6遞歸模式。這種遞歸模式屬于第三種情況，子問題的解決先后順序是有關系的。

第三步，根據遞歸模式編寫相應的程序代碼。

需要注意的是，在第三種遞歸模式中，多個子問題的解決順序是有關聯的。上面的方法是先解決最后一個位置，再解決子數組的排序。還有一種方法是先解決子數組的排序，再確定最后一個位置的數據。讀者可以試著用這一種方法設計遞歸算法。

進一步拓寬學生的思路，換一種分解方法，將第一個位置分離出來，遞歸模式也是屬于第三種情況。

5 結 語

將計算思維引入到遞歸算法的教學中來，在不改變教學內容的基礎上，改進教學方法，有意識地將與計算思維相關的問題分解、抽象和自動化的方法自然地融入到教學中，使原有的教學活動上升到計算思維的新高度。

在遞歸教學中引入計算思維，不是在原有內容上貼上計算思維標簽，將所有的迭代算法用遞歸算法代替；而是提煉并展現隱藏在這些算法設計后面的計算思維方法，引起學生學習興趣和心理共鳴。

在遞歸算法的教學中利用遞歸模式降低教學難度。使原先學生難以理解、教師經常弱化的遞歸教學變得容易，教師也不再忐忑不安。從宏觀上分析問題，通過分解，抽象出遞歸模式，無論對理工類還是文科類的學生都很容易接受。

通過教學方法的改革，同時也拓展了課程的深度。將學生學習過的算法修改成遞歸的算法，再與原來的算法進行比較，更容易引發學生的學習興趣。教師引導學生將遞歸算法和迭代算法進行比較，使學生對遞歸和迭代這兩種算法有更深入的理解，不僅鞏固了學到的知識，更重要的是提升了學生分析問題、解決問題的能力。

參考文獻：

[1] 陳國良， 董榮勝. 計算思維與大學計算機基礎教育[J]. 中國大學教學， 2011（1）： 7-11.

[2] 李廉. 計算思維： 概念與挑戰[J]. 中國大學教學， 2012（1）： 7-12.

[3] 龔沛曾， 楊志強. 大學計算機基礎教學中的計算思維培養育[J]. 中國大學教學， 2012（5）： 51-54.

[4] 馮博琴. 對于計算思維能力培養“落地”問題的探討[J]. 中國大學教學， 2012（9）： 6-9.

（編輯：彭遠紅）