對遞歸算法進行“分類探討”的教學方法研究

范昊　束德勤

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

關鍵詞：遞歸算法;典型案例;遞歸程序框架;算法分類

中圖分類號：G642.0? ? ?文獻標志碼：A? ? ?文章編號：1674-9324（2020）16-0195-02

一、引言

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

二、遞歸問題的本質

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

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

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

三、遞歸算法的分類

在教學的課堂講授階段，教師可以根據遞歸的不同特點，將遞歸程序分類。按照遞歸調用時，遞歸語句在程序中出現的位置可以將遞歸程序分類為：順序調用遞歸、分支調用遞歸和循環調用遞歸。下面本文分別給出實例。

1.順序調用遞歸。此類遞歸程序結構往往比較簡單，指遞歸調用語句出現在程序的順序執行語句中，遞歸程序在調用處執行，執行完畢返回到調用處的后續語句。如求階乘、斐波那契數列、樹的前中后序遍歷等。

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

3.循環調用遞歸。此類遞歸程序最為復雜，也是學生最不好理解的一類遞歸。遞歸調用語句出現在循環語句中，如for、while循環中，在循環中進行遞歸調用。有時很多程序還得結合判斷條件，在循環中符合條件的情況遞歸調用，不符合條件的不調用，調用結束后返回本層循環語句繼續下一個循環變量的調用。這類程序如圖的深度優先遍歷、求一個集合的全排列、八皇后問題等。以深度優先遍歷為例，見圖1。

四、課堂講授案例

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

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

3.遞歸程序設計。根據上述分析，循環遞歸調用的程序設計如圖2所示。

五、結束語

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

參考文獻：

[1]項響琴.遞歸問題的教學探討[J].合肥學院學報，2016，6.

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

[3]范昊，束德勤.《數據結構》教學方法研究[J].教育教學論壇，2019，47：195-196.

[4]劉羿，虎曉紅，孫昌霞.高度信息化形式下高校計算機基礎課程教學探析[J].教育教學論壇，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

基金項目：2019教育部產學合作協同育人項目（面向企業需求的學生創新能力培養模式研究）項目編號：201901117012

作者簡介：范昊（1977-），男，山東泰安人，副教授，主要研究方向為算法設計與分析、Petri網理論與應用、深度學習等。

通訊作者：束德勤（1978-），女，山東淄博人，副教授，主要研究方向為計算機網絡、Petri網理論與應用等。