數(shù)據(jù)結(jié)構(gòu)中遞歸算法的教學(xué)研究

摘 ?要：遞歸是程序設(shè)計(jì)中一個(gè)強(qiáng)有力的工具，其在數(shù)據(jù)結(jié)構(gòu)中經(jīng)常被用到。但是目前普通高校學(xué)生不能真正深入理解并掌握教材中關(guān)于遞歸及遞歸算法的內(nèi)容，尤其是遞歸調(diào)用的復(fù)雜過(guò)程。文章研究了基于代碼的遞歸調(diào)用過(guò)程圖以及遞歸調(diào)用棧和棧幀變化圖，提出了基于這兩種圖的遞歸調(diào)用過(guò)程教學(xué)法。將其應(yīng)用于教學(xué)實(shí)踐中，有效提高了學(xué)生理解遞歸的調(diào)用和執(zhí)行過(guò)程，教學(xué)取得了明顯的成效。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);遞歸算法;遞歸調(diào)用;遞歸調(diào)用棧;棧幀

中圖分類號(hào)：TP311.1 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）13-0188-04

Abstract：Recursion is a powerful tool for programming design and often used in data structure. However，currently it is hard for students in ordinary universities to deeply understand and master the content of recursion and recursive algorithm in the text books，especially the complex process of recursive calls. The article studied the graph of code based recursive call process as well as the graph of recursive call stack and stack frame，and proposed the instruction approach of the recursive call process based on the two graphs. The proposed approach was applied in the instruction practice. It effectively improved the understanding of the students for the process of recursive calls and execution. Teaching has achieved remarkable results.

Keywords：data structure;recursive algorithm;recursive call;recursive call stack;stack frame

0 ?引 ?言

遞歸是程序設(shè)計(jì)中一個(gè)強(qiáng)有力的工具，在數(shù)據(jù)結(jié)構(gòu)中經(jīng)常被用到。筆者曾通過(guò)把遞歸算法同時(shí)應(yīng)用到后端以及前端代碼，實(shí)現(xiàn)了數(shù)據(jù)庫(kù)后端數(shù)據(jù)驅(qū)動(dòng)到前端動(dòng)態(tài)遞歸結(jié)構(gòu)的網(wǎng)頁(yè)自動(dòng)生成框架，成功解決了公司的問(wèn)題。在開發(fā)過(guò)程中，要把遞歸算法與前端的AngularJS框架中的Directive以及眾多的其他前端控件融合在一起，如沒(méi)有深入了解遞歸算法的原理和調(diào)用執(zhí)行過(guò)程是不可能成功的。但是，現(xiàn)有的教材和教學(xué)方法缺乏足夠的內(nèi)容和方法去幫助學(xué)生透徹理解遞歸調(diào)用和執(zhí)行的復(fù)雜過(guò)程，因此普通高校的學(xué)生不能很好地掌握該知識(shí)。

1 ?遞歸算法及其重要性

遞歸具體指一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中直接或間接調(diào)用自身的一種方法[1]。遞歸不僅是數(shù)學(xué)中的一個(gè)重要概念，也是計(jì)算機(jī)程序設(shè)計(jì)中一個(gè)強(qiáng)有力的工具。在如下三種情況下都要用到遞歸。其一，有很多數(shù)學(xué)函數(shù)是遞歸定義，如本文將要舉例的階乘函數(shù);其二，有的數(shù)據(jù)結(jié)構(gòu)，如二叉樹、廣義表等，由于結(jié)構(gòu)本身固有的遞歸特性，則它們的操作可遞歸地描述;其三，還有一類問(wèn)題，雖然問(wèn)題本身沒(méi)有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比迭代求解簡(jiǎn)單，如Hanoi塔問(wèn)題[2]?！皵?shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)專業(yè)中涉及編程的核心基礎(chǔ)課程，常見的數(shù)據(jù)結(jié)構(gòu)介紹中，有一半左右的章節(jié)用到遞歸算法。如廣義表、樹、圖、查找、排序等。由此可以看出，遞歸相當(dāng)廣泛地應(yīng)用與計(jì)算機(jī)領(lǐng)域。

2 ?目前教學(xué)中存在的問(wèn)題

由于遞歸的特點(diǎn)是用少量的代碼描述解題過(guò)程中的多次重復(fù)。其簡(jiǎn)潔的代碼背后隱含了嵌套、遞歸的很多內(nèi)容。例如，遞歸函數(shù)中在調(diào)用自己的代碼的操作與其下一步操作之間，從代碼來(lái)看是緊鄰的關(guān)系;但是程序?qū)嶋H調(diào)用和運(yùn)行中，它們之間可能經(jīng)歷了非常多的過(guò)程和步驟。一個(gè)遞歸函數(shù)的調(diào)用，根據(jù)調(diào)用參數(shù)的情況，可能隱含了無(wú)數(shù)次的遞歸調(diào)用。直到遞歸出口，才開始層層回溯，最后才能執(zhí)行到遞歸調(diào)用操作之后的代碼。由于反復(fù)多次的調(diào)用，代碼執(zhí)行的整個(gè)過(guò)程的來(lái)處和去處，很容易被混淆。但是，現(xiàn)有的教材主要講述遞歸模型并展示遞歸的分解和求解的簡(jiǎn)單示意圖，沒(méi)有詳細(xì)深入地剖析調(diào)用過(guò)程，因此學(xué)生不清楚代碼執(zhí)行過(guò)程，同時(shí)對(duì)為什么遞歸可能會(huì)消耗很大的內(nèi)存、為什么使用遞歸要謹(jǐn)慎、為什么遞歸效率低沒(méi)有清晰的認(rèn)識(shí)。在學(xué)習(xí)這部分內(nèi)容時(shí)，尤其是在普通高校學(xué)生基礎(chǔ)相對(duì)不夠扎實(shí)的情況下，很少同學(xué)真正了解遞歸程序?qū)嶋H的運(yùn)行過(guò)程，因此無(wú)法真正掌握遞歸的精髓并正確運(yùn)用。

3 ?教學(xué)中如何改進(jìn)

下面以求自然數(shù)的階乘函數(shù)n！為例講解筆者在教學(xué)中的改進(jìn)，主要從更深入的遞歸分解和求解過(guò)程以及遞歸調(diào)用棧與棧幀兩大方面作為突破口。

代碼如下：

Int ftrl （int n）

{

If （n==1） {//line1

return 1; //line2

}//line3

Int pre = ftrl （n-1）; ? //line4

return pre * n; ? ? ? //line5

}

void main（）

{

Int a = 3， b; ? ? ? ? ?//line1

b = ftrl（a）; ? ? ? ? ? //line2

printf（“b：%d＼n”， b）; ? ?//line3

}

代碼包含一個(gè)main函數(shù)，在main函數(shù)中調(diào)用函數(shù)ftrl（）。由于在ftrl（）中，代碼的第四行重復(fù)調(diào)用本函數(shù)，只是減小了參數(shù)，因此ftrl是一個(gè)遞歸函數(shù)。

3.1 ?遞歸分解和求解過(guò)程

在常見的講解中，遞歸分解和求解的過(guò)程如圖1所示[3，4]。

圖1中能清楚地看到求解ftrl（3）的過(guò)程被逐步分解成求解ftrl（2）和ftrl（1）的過(guò)程，ftrl（1）是遞歸出口，可以直接求值。遞歸從這里開始層層回溯，也就是ftrl（1）的值求出后返回給ftrl（2），ftrl（2）的值求出后返回給ftrl（3），ftrl（3）調(diào)用結(jié)束返回給main函數(shù)。上述過(guò)程中對(duì)遞歸總體的調(diào)用情況解釋地比較清楚，但圖1無(wú)法給出遞歸調(diào)用執(zhí)行的詳細(xì)過(guò)程、多次遞歸調(diào)用中遞歸體內(nèi)代碼執(zhí)行的先后順序。在普通院校中，大部分學(xué)生深入鉆研復(fù)雜問(wèn)題的能力相對(duì)有限，因此對(duì)于遞歸這樣表面簡(jiǎn)單、實(shí)際復(fù)雜的內(nèi)容，教師必須帶領(lǐng)學(xué)生把過(guò)程剖析清楚。

相對(duì)只有遞歸函數(shù)名和參數(shù)的圖1，圖2增加了遞歸函數(shù)的內(nèi)部代碼[5]，可以更清楚地看到每層代碼，尤其是遞歸調(diào)用代碼之后的代碼與其他層代碼的執(zhí)行順序關(guān)系。這是圖1無(wú)法表達(dá)的極其重要的內(nèi)容，也是遞歸最復(fù)雜的地方。在前面給出的代碼中，函數(shù)入口main函數(shù)里調(diào)用了遞歸函數(shù)ftrl（3）。圖2從ftrl（3）開始展開，ftrl（3）為第一次遞歸調(diào)用，圖2展示了ftrl（2）被調(diào)用的位置在ftrl（3）代碼內(nèi)部的第四行：Int pre=ftrl（3-1）。順著調(diào)用ftrl（2）（第二次遞歸調(diào)用）的箭頭方向，ftrl（1）（第三次遞歸調(diào)用）在ftrl（2）中的第4行被調(diào)用。圖中也標(biāo)明了ftrl（1）的值返回給ftrl（2）、ftrl（2）的值返回給ftrl（3）。第二次、第三次遞歸調(diào)用在圖中使用斜體表示，只有等第二、三次遞歸調(diào)用執(zhí)行完畢，ftrl（3-1）也就是ftrl（2）才算結(jié)束。ftrl（2）調(diào)用結(jié)束后程序應(yīng)該返回的位置是ftrl函數(shù)內(nèi)部遞歸體代碼line4：Int pre=ftrl（3-1）。這行代碼實(shí)際上包含兩條計(jì)算機(jī)指令：第一條是調(diào)用ftrl（2）;第二條是把ftrl（2）的返回值賦給局部變量pre。因此，圖2中ftrl（2）執(zhí)行完畢返回ftrl（3）中原來(lái)調(diào)用它的地方，也是返回到第二條指令的內(nèi)存地址，并開始執(zhí)行第二條指令：給pre賦值。圖中Int pre=下的下劃線表示其執(zhí)行順序是在ftrl（2）和ftrl（1）執(zhí)行之后，也就是圖中所有斜體代碼執(zhí)行完之后。給pre的賦值操作完成后，再繼續(xù)執(zhí)行下面的代碼line5：return pre*3，這行代碼的下劃線含義同上。所以，line4 Int pre=ftrl（3-1）一行代碼包含兩條指令，而且這兩條指令之間隱含了ftrl（2）和ftrl（1）執(zhí)行的全過(guò)程。這個(gè)地方如果不詳細(xì)講解，大多數(shù)學(xué)生很難想清楚。同理，在其他層的ftrl遞歸調(diào)用中，例如ftrl（2）的函數(shù)體內(nèi)，調(diào)用和返回ftrl（1）的過(guò)程也是一樣的，在此不贅述。在沒(méi)有詳細(xì)剖析前，如果提問(wèn)學(xué)生在某次遞歸函數(shù)體執(zhí)行完畢退出后的返回位置，很難得到正確答案。但經(jīng)過(guò)以上步驟明確地、深入細(xì)致地分析和講解，學(xué)生能立即回答出：無(wú)論哪一層遞歸調(diào)用結(jié)束后，都會(huì)返回上一層調(diào)用它的地方的下一條指令處并繼續(xù)執(zhí)行。

3.2 ?遞歸調(diào)用棧與棧幀

遞歸代碼非常簡(jiǎn)潔，理解了遞歸原理，其思想能解決很多問(wèn)題。但是遞歸調(diào)用過(guò)程中可能會(huì)占用很大的內(nèi)存，甚至可能導(dǎo)致系統(tǒng)棧溢出。遞歸函數(shù)的執(zhí)行效率低，所以書上會(huì)提到，使用遞歸函數(shù)要謹(jǐn)慎，如果不必要盡量少用。原因是遞歸算法要通過(guò)棧來(lái)實(shí)現(xiàn)，才能夠保證遞歸的正確調(diào)用和返回。每一次函數(shù)的調(diào)用，都會(huì)在調(diào)用棧（Call Stack）上維護(hù)一個(gè)獨(dú)立的棧幀（Stack Frame）。棧幀中保存了函數(shù)參數(shù)，函數(shù)的局部變量，函數(shù)執(zhí)行完成后的返回地址等數(shù)據(jù)[6]。圖3顯示了從main函數(shù)調(diào)用ftrl遞歸函數(shù)的過(guò)程中棧和棧幀的變化情況，圖中每一條記錄即每一行都是一個(gè)棧幀。

圖3中自上而下的第一部分是main函數(shù)的棧幀，a、b都是局部變量，其中a已經(jīng)有初值，b還沒(méi)有。在main函數(shù)中調(diào)用ftrl（3），main函數(shù)的執(zhí)行會(huì)暫時(shí)在這里中斷而跳轉(zhuǎn)去執(zhí)行ftrl（3），所以要在main（調(diào)用者）的棧幀中保留ftrl（3）（被調(diào)用者）執(zhí)行完成后的返回地址。類似前面的Int pre=ftrl（3-1），代碼b=ftrl（3）也是包含了兩條計(jì)算機(jī)指令，一是調(diào)用ftrl（3），二是把ftrl（3）的返回值賦值給b，因此該指令的內(nèi)存地址就是ftrl（3）的返回地址。

圖3的第二部分是ftrl（3）被調(diào)用后棧和棧幀的情況。就是在main函數(shù)的棧幀上加上ftrl（3）的棧幀。在ftrl（3）的棧幀中，n是函數(shù)參數(shù)，3是從main函數(shù)傳過(guò)來(lái)的;pre是局部變量，目前還沒(méi)有值，需要等到ftrl（2）調(diào)用執(zhí)行完成后將其返回值賦給pre。同樣，在ftrl（3）中調(diào)用ftrl（2），程序要在這里中斷并跳轉(zhuǎn)，就需要在ftrl（3）的棧幀中保存ftrl（2）的返回地址，這個(gè)地址就是把ftrl（2）的結(jié)果賦值給pre的指令的內(nèi)存地址。

圖3中的第三部分是ftrl（2）被調(diào)用后棧和棧幀的情況圖。就是在ftrl（3）的棧幀上加上ftrl（2）的棧幀。在ftrl（2）的棧幀中，n是函數(shù)參數(shù)，2是在ftrl（3）中被調(diào)用時(shí)傳過(guò)來(lái)的，ftrl（2）的棧幀的其它說(shuō)明與上面ftrl（3）的很相似，就不贅述。

在ftrl（2）中調(diào)用ftrl（1），添加ftrl（1）的棧幀。因?yàn)閒trl（3）和ftrl（2）都不能直接求解，所以一直都是壓棧的過(guò)程。直到ftrl（1）被ftrl（2）調(diào)用時(shí)，ftrl（1）能被直接求解，這時(shí)到了遞歸出口。這就是圖3的第四部分，棧頂是ftrl（1）的棧幀，其函數(shù)參數(shù)是1。在執(zhí)行ftrl（1）時(shí)，滿足if條件，因此直接返回1。遞歸到此開始退棧。

在圖的第五部分，ftrl（1）的棧幀退出。ftrl（1）把返回值1賦給ftrl（2）的pre變量。隨后，圖的第六部分ftrl（2）退棧并把返回結(jié)果2賦值給ftrl（3）中的pre局部變量。之后，圖的第七部分ftrl（3）的棧幀退棧并把返回值6返回給main函數(shù)的局部變量b。最后，圖的第八部分main函數(shù)的棧幀退棧，main函數(shù)中輸出b的值到屏幕?？梢钥吹?，函數(shù)的局部變量越多，遞歸調(diào)用的層次越深，內(nèi)存占用就越大，因?yàn)闂４嬖谟趦?nèi)存空間。內(nèi)存占用嚴(yán)重時(shí)，例如由于遞歸算法的錯(cuò)誤導(dǎo)致遞歸不能結(jié)束，可能造成內(nèi)存消耗殆盡導(dǎo)致系統(tǒng)崩潰。這就是要慎用遞歸的原因，也是我們要真正透徹掌握遞歸原理和調(diào)用過(guò)程的原因，在沒(méi)有真正掌握時(shí)使用很容易出錯(cuò)。遞歸調(diào)用這樣不斷壓棧、退棧的過(guò)程，消耗的時(shí)間和空間資源都大，所以遞歸算法執(zhí)行效率不高。

筆者在廣西百色學(xué)院計(jì)算機(jī)系“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)中，用含代碼的遞歸調(diào)用過(guò)程圖（圖2）和遞歸調(diào)用的棧和棧幀變化圖（圖3），為學(xué)生講解遞歸算法的遞歸調(diào)用過(guò)程，并布置了相應(yīng)的練習(xí)作業(yè)。通過(guò)課堂的講解，調(diào)動(dòng)同學(xué)們的好奇心和求知欲，促使其自行探索;學(xué)生在完成作業(yè)時(shí)展開遞歸調(diào)用圖的過(guò)程，可以使他們充分明白遞歸的含義和細(xì)節(jié)，最終教學(xué)取得了令人滿意的效果。

4 ?結(jié) ?論

本文簡(jiǎn)要介紹了遞歸算法以及它在計(jì)算機(jī)領(lǐng)域的重要性，說(shuō)明了在目前普通高?！皵?shù)據(jù)結(jié)構(gòu)”課程遞歸算法教學(xué)中存在的不足，并提出了改進(jìn)的意見。筆者將這種方法用于自己的教學(xué)實(shí)踐中，調(diào)動(dòng)了學(xué)生的好奇心和潛在的求知欲，教學(xué)取得了明顯的收效。

參考文獻(xiàn)：

[1] 百度百科.遞歸 [EB/OL].（2015-01-23）.https：//baike.baidu.com/item/%E9%80%92%E5%BD%92/1740695？fr=aladdin.

[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） [M].北京：清華大學(xué)出版社，2007.

[3] 李春葆.數(shù)據(jù)結(jié)構(gòu)教程：第5版 [M].北京：清華大學(xué)出版社，2017.

[4] 牛思先.數(shù)據(jù)結(jié)構(gòu)：第6章遞歸 [EB/OL].（2020-05-06）.https：//ke.qq.com/webcourse/index.html#cid=1206810&term_id=101303509&taid=26367238&lite=1&vid=5285890802680286916.

[5] 傳智播客.數(shù)據(jù)結(jié)構(gòu)與算法——C語(yǔ)言版 [M].北京：清華大學(xué)出版社，2016.

[6] 鐵甲萬(wàn)能狗.第4篇：戲說(shuō)程序棧-棧幀 [EB/OL].（2019. 10.18）.https：//www.jianshu.com/p/69d7b205df33.

作者簡(jiǎn)介：宋衛(wèi)紅（1968—），女，漢族，云南昆明人，計(jì)算機(jī)專任教師，博士，研究方向：描述邏輯推理、知識(shí)推理、知識(shí)圖譜。