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

朱君波+龔沛曾+楊志強

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

關(guān)鍵詞：計算思維；程序設(shè)計；遞歸算法；教學(xué)改革

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

中圖分類號：G642

0 引 言

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

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

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

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

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

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

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

2 遞歸教學(xué)的新認識

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

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

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

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

并給出其對應(yīng)的遞歸函數(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)象，引導(dǎo)學(xué)生理解遞歸的實質(zhì)是“分而治之”“大問題分解為本質(zhì)相同的小問題”的思想，如圖2所示。問題分解是計算思維的典型方法，也是遞歸算法的核心思想，應(yīng)貫穿于分析和設(shè)計遞歸函數(shù)的始終。

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

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

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

2.4 利用計算思維的方法設(shè)計遞歸算法

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

3 以遞歸模式為中心的遞歸算法設(shè)計

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

3.1 問題分解

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

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

3.2 抽 象

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

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

3.3 自動化

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

4 遞歸案例

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

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

4.1 整數(shù)處理

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

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

第二步，抽象出遞歸模式。被除數(shù)m（大問題）和商m＼10（小問題）與余數(shù)（小問題）的邏輯關(guān)系是：m的位數(shù)等于商的位數(shù)+1，與余數(shù)無關(guān)。屬于第一種遞歸模式，只要得到商的位數(shù)（遞歸調(diào)用獲得），則被除數(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ù)字子串通過遞歸調(diào)用獲得。因此，得到如圖4所示的遞歸模式。

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

4.3 數(shù)組處理

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

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

例如，將數(shù)組a中的0～n個數(shù)進行按位置（下標）遞增排序，遞歸的排序過程名設(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ù)組排序（遞歸調(diào)用sort（a，n-1）實現(xiàn)），得到如圖6遞歸模式。這種遞歸模式屬于第三種情況，子問題的解決先后順序是有關(guān)系的。

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

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

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

5 結(jié) 語

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

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

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

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

參考文獻：

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

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

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

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

（編輯：彭遠紅）