對(duì)遞歸算法進(jìn)行“分類探討”的教學(xué)方法研究

范昊　束德勤

摘要：遞歸算法或者遞歸程序是計(jì)算機(jī)及相關(guān)專業(yè)高校學(xué)生，在大學(xué)學(xué)習(xí)階段必須掌握的一種程序設(shè)計(jì)方法。文章首先分析了高校學(xué)生在學(xué)習(xí)遞歸算法時(shí)遇到的難點(diǎn)，然后將遞歸算法進(jìn)行不同角度的分類，由易到難詳細(xì)剖析遞歸算法的設(shè)計(jì)思路，最后對(duì)遞歸程序的設(shè)計(jì)過(guò)程進(jìn)行講解和總結(jié)。文中還結(jié)合了實(shí)際教學(xué)案例，給出了遞歸算法的講解和設(shè)計(jì)過(guò)程。

關(guān)鍵詞：遞歸算法;典型案例;遞歸程序框架;算法分類

中圖分類號(hào)：G642.0? ? ?文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：1674-9324（2020）16-0195-02

一、引言

計(jì)算機(jī)及相關(guān)專業(yè)在大學(xué)本專科的學(xué)習(xí)過(guò)程中，不可避免地要接觸到遞歸程序的設(shè)計(jì)[1]。遞歸算法的概念和設(shè)計(jì)技巧，貫穿于計(jì)算機(jī)及相關(guān)專業(yè)本科學(xué)習(xí)的各個(gè)階段。遞歸思想也在程序設(shè)計(jì)、算法分析甚至數(shù)學(xué)課程中有所應(yīng)用。遞歸不是一門專門的課程，更不是專門的一個(gè)學(xué)科，而是一種思想、一種思路，在大學(xué)中的各門課程中都有它的身影，甚至在我們的生活中也處處可見(jiàn)。但很多學(xué)生一直感覺(jué)遞歸程序是一個(gè)難點(diǎn)問(wèn)題，甚至對(duì)遞歸程序的執(zhí)行過(guò)程掌握得都不是很清楚[2，3]。針對(duì)這些問(wèn)題，本文詳細(xì)分析和講解遞歸的執(zhí)行過(guò)程和遞歸程序的設(shè)計(jì)技巧。對(duì)遞歸程序設(shè)計(jì)過(guò)程中的各種情況進(jìn)行詳細(xì)的分類探討，使得教師在講解時(shí)有的放矢，學(xué)生們?cè)诶斫鈺r(shí)層層深入，對(duì)遞歸的本質(zhì)有更深入的了解。

二、遞歸問(wèn)題的本質(zhì)

1.遞歸算法的基本概念。遞歸程序（recursion algorithm）在計(jì)算機(jī)科學(xué)中指的是一種通過(guò)重復(fù)求解子問(wèn)題，將問(wèn)題分解為同類的更小問(wèn)題而解決原始問(wèn)題的設(shè)計(jì)方法[4]。遞歸算法可以被應(yīng)用以解決很多計(jì)算機(jī)科學(xué)中的實(shí)際問(wèn)題甚至是生活中息息相關(guān)的問(wèn)題，因此它不僅僅是計(jì)算機(jī)學(xué)科中的一個(gè)基本概念，更多的是一種計(jì)算思維和解決問(wèn)題的思路。很多程序設(shè)計(jì)語(yǔ)言支持函數(shù)的直接調(diào)用自身或者間接調(diào)用自身，在一些語(yǔ)言中，如C、C++、Java等程序設(shè)計(jì)語(yǔ)言，函數(shù)或者子程序可以通過(guò)調(diào)用自身來(lái)進(jìn)行遞歸。

2.遞歸程序的特點(diǎn)。其實(shí)，簡(jiǎn)單來(lái)說(shuō)，遞歸算法的本質(zhì)是把原始問(wèn)題歸結(jié)為規(guī)模更小的同類問(wèn)題的子問(wèn)題，子問(wèn)題再分解為更小子問(wèn)題，直到最小子問(wèn)題直接得到答案，或者非常容易解決，然后層層返回，得到原問(wèn)題的解。遞歸的基本特點(diǎn)為：（1）每一級(jí)的函數(shù)調(diào)用自己有的參數(shù)或者變量，當(dāng)然變量有局部變量和全局變量。（2）每一次函數(shù)自身調(diào)用都會(huì)有返回，不一定立即返回，有時(shí)是多層調(diào)用后返回，有時(shí)是循環(huán)中返回。（3）遞歸函數(shù)中，遞歸調(diào)用前程序語(yǔ)句和各級(jí)被調(diào)用子程序或者循環(huán)中調(diào)用的子程序具有同樣的執(zhí)行方式。（4）遞歸程序中，位于遞歸子程序調(diào)用后的語(yǔ)句，其執(zhí)行順序和各個(gè)被調(diào)用子程序的執(zhí)行順序相反。

3.遞歸程序設(shè)計(jì)的要點(diǎn)。第一要點(diǎn)：明確這個(gè)程序想要解決什么問(wèn)題。姑且不管子程序里面的代碼是什么，首先要明確正在設(shè)計(jì)的程序的功能是什么，要完成什么工作。第二要點(diǎn)：合理設(shè)計(jì)遞歸結(jié)束條件。需要設(shè)計(jì)者找出條件為什么時(shí)，可能是變量值，也可能是函數(shù)的參數(shù)是多少時(shí)，遞歸結(jié)束，然后遞歸程序直接返回結(jié)果。第三要點(diǎn)：找出程序的遞推關(guān)系算式。設(shè)計(jì)者不斷縮小參數(shù)的范圍，把原問(wèn)題不斷縮小，使程序中的遞推關(guān)系保持不變。

三、遞歸算法的分類

在教學(xué)的課堂講授階段，教師可以根據(jù)遞歸的不同特點(diǎn)，將遞歸程序分類。按照遞歸調(diào)用時(shí)，遞歸語(yǔ)句在程序中出現(xiàn)的位置可以將遞歸程序分類為：順序調(diào)用遞歸、分支調(diào)用遞歸和循環(huán)調(diào)用遞歸。下面本文分別給出實(shí)例。

1.順序調(diào)用遞歸。此類遞歸程序結(jié)構(gòu)往往比較簡(jiǎn)單，指遞歸調(diào)用語(yǔ)句出現(xiàn)在程序的順序執(zhí)行語(yǔ)句中，遞歸程序在調(diào)用處執(zhí)行，執(zhí)行完畢返回到調(diào)用處的后續(xù)語(yǔ)句。如求階乘、斐波那契數(shù)列、樹(shù)的前中后序遍歷等。

2.分支調(diào)用遞歸。此類遞歸程序往往包含分支語(yǔ)句，也就是說(shuō)程序在進(jìn)行運(yùn)算時(shí)，要根據(jù)需要解決的問(wèn)題的實(shí)際需求，分不同情況進(jìn)行遞歸調(diào)用，遞歸調(diào)用時(shí)不同分支調(diào)用的參數(shù)往往不同。這類程序包含整數(shù)劃分問(wèn)題、二分查找問(wèn)題、快速排序等，以整數(shù)劃分問(wèn)題為例最為典型。

3.循環(huán)調(diào)用遞歸。此類遞歸程序最為復(fù)雜，也是學(xué)生最不好理解的一類遞歸。遞歸調(diào)用語(yǔ)句出現(xiàn)在循環(huán)語(yǔ)句中，如for、while循環(huán)中，在循環(huán)中進(jìn)行遞歸調(diào)用。有時(shí)很多程序還得結(jié)合判斷條件，在循環(huán)中符合條件的情況遞歸調(diào)用，不符合條件的不調(diào)用，調(diào)用結(jié)束后返回本層循環(huán)語(yǔ)句繼續(xù)下一個(gè)循環(huán)變量的調(diào)用。這類程序如圖的深度優(yōu)先遍歷、求一個(gè)集合的全排列、八皇后問(wèn)題等。以深度優(yōu)先遍歷為例，見(jiàn)圖1。

四、課堂講授案例

1.以趣味問(wèn)題引入遞歸。八皇后問(wèn)題，是一個(gè)古老并且非常著名的算法問(wèn)，它是遞歸算法的經(jīng)典例題。這個(gè)問(wèn)題由國(guó)際象棋棋手馬克斯·貝瑟爾于1848年提出。在8×8格的棋盤上擺放8個(gè)皇后棋子，給定任意兩個(gè)皇后使得它們不能處于同一行、同一列或同一斜線上，請(qǐng)問(wèn)有多少種布局的方法。數(shù)學(xué)家高斯起初認(rèn)為有76種方案，后來(lái)有人用圖論的方法知道正確答案是92種解法。

2.問(wèn)題的解法思路。由于棋盤一行或者一列只可以放置一個(gè)皇后，就可以用一維數(shù)組X（x1，x2，…，xn），表示第i列皇后所在的行x[i]，所以用一維數(shù)組來(lái)表示各個(gè)皇后的位置就可以。對(duì)于每一行的皇后可以放置在1，2，…，n各個(gè)列同時(shí)還不能和已經(jīng)放置的皇后有沖突，所以很顯然，該遞歸程序的設(shè)計(jì)是循環(huán)遞歸調(diào)用的方法。

3.遞歸程序設(shè)計(jì)。根據(jù)上述分析，循環(huán)遞歸調(diào)用的程序設(shè)計(jì)如圖2所示。

五、結(jié)束語(yǔ)

為了使學(xué)生們很好地掌握遞歸這一貫穿于大學(xué)計(jì)算機(jī)相關(guān)專業(yè)各個(gè)階段的算法，本文首先給出了遞歸問(wèn)題的本質(zhì)和遞歸程序本身的特點(diǎn)，分析了學(xué)生們?cè)谡莆者@類算法或者程序時(shí)容易出現(xiàn)的問(wèn)題。然后結(jié)合實(shí)際教學(xué)情況對(duì)遞歸程序進(jìn)行了分類，從簡(jiǎn)單到復(fù)雜把各種遞歸程序出現(xiàn)的情況做了詳細(xì)的總結(jié)，便于教師課堂講授和學(xué)生分類學(xué)習(xí)。最后給出了一個(gè)實(shí)際的教學(xué)實(shí)例，詳細(xì)講述了遞歸程序的設(shè)計(jì)思路和步驟。通過(guò)本文分析，使得遞歸問(wèn)題可以實(shí)現(xiàn)趣味性教學(xué)，并使學(xué)生對(duì)課程感興趣且更易學(xué)會(huì)。

參考文獻(xiàn)：

[1]項(xiàng)響琴.遞歸問(wèn)題的教學(xué)探討[J].合肥學(xué)院學(xué)報(bào)，2016，6.

[2]朱浩.基于自組織理論的研究生創(chuàng)新思維生成與培養(yǎng)機(jī)制研究[J].研究生教育，2015，4（4）：22-26.

[3]范昊，束德勤.《數(shù)據(jù)結(jié)構(gòu)》教學(xué)方法研究[J].教育教學(xué)論壇，2019，47：195-196.

[4]劉羿，虎曉紅，孫昌霞.高度信息化形式下高校計(jì)算機(jī)基礎(chǔ)課程教學(xué)探析[J].教育教學(xué)論壇，2019，47：197-199.

Research on the Teaching Method of "Classification Discussion" on Recursive Algorithm

FAN Hao，SHU De-qin

（College of Information Science and Engineering，Shandong Agricultural University，Tai'an，Shandong 271018，China）

Abstract：Recursion algorithm or recursion program is a kind of program design method that must be mastered by college students majoring in computer and related majors in the university learning stage.This paper first analyzes the difficulties college students encounter in learning recursive algorithm，analyzes the nature and characteristics of recursive program，then classifies the recursive algorithm from different angles，and finally explains and summarizes the design process of recursive program.The paper also gives the explanation and design process of recursive algorithm.This method has a good practical application effect on the teaching and research of recursive algorithm.

Key words：recursion algorithm;typical cases;recursion programming framework;algorithmic classification

收稿日期：2019-10-20

基金項(xiàng)目：2019教育部產(chǎn)學(xué)合作協(xié)同育人項(xiàng)目（面向企業(yè)需求的學(xué)生創(chuàng)新能力培養(yǎng)模式研究）項(xiàng)目編號(hào)：201901117012

作者簡(jiǎn)介：范昊（1977-），男，山東泰安人，副教授，主要研究方向?yàn)樗惴ㄔO(shè)計(jì)與分析、Petri網(wǎng)理論與應(yīng)用、深度學(xué)習(xí)等。

通訊作者：束德勤（1978-），女，山東淄博人，副教授，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、Petri網(wǎng)理論與應(yīng)用等。