范昊　束德勤

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

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

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

一、引言

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

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

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

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

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

三、遞歸算法的分類

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

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

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

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

四、課堂講授案例

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

2.問題的解法思路。由于棋盤一行或者一列只可以放置一個(gè)皇后，就可以用一維數(shù)組X（x1，x2，…，xn），表示第i列皇后所在的行x[i]，所以用一維數(shù)組來表示各個(gè)皇后的位置就可以。對于每一行的皇后可以放置在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é)束語

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

參考文獻(xiàn)：

[1]項(xiàng)響琴.遞歸問題的教學(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)目編號：201901117012

作者簡介：范昊（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)用等。