朱君波+龔沛曾+楊志強

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

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

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

中圖分類號：G642

0 引 言

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

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

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

1 傳統(tǒng)的遞歸教學

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

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

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

2 遞歸教學的新認識

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

2.1 認識遞歸現(xiàn)象

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

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

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

Function f#（ByVal n% ）

If （ n < 2 ） Then

f=1

Else

f=n*f（n-1）

End If

End Function

2.2 遞歸核心思想

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

2.3 遞歸的執(zhí)行過程

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

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

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

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

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

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

3.1 問題分解

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

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

3.2 抽 象

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

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

3.3 自動化

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

4 遞歸案例

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

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

4.1 整數(shù)處理

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

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

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

第三步，根據(jù)遞歸模式編寫遞歸函數(shù)：

Function fig%（ByVal m%）

If m ＼ 10 = 0 Then

fig = 1

Else

fig = fig（m ＼ 10） + 1

End If

End Function

4.2 字符串處理

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

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

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

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

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

4.3 數(shù)組處理

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

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

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

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

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

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

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

5 結 語

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

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

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

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

參考文獻：

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

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

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

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

（編輯：彭遠紅）