數據結構中遞歸算法的教學研究

摘 ?要：遞歸是程序設計中一個強有力的工具，其在數據結構中經常被用到。但是目前普通高校學生不能真正深入理解并掌握教材中關于遞歸及遞歸算法的內容，尤其是遞歸調用的復雜過程。文章研究了基于代碼的遞歸調用過程圖以及遞歸調用棧和棧幀變化圖，提出了基于這兩種圖的遞歸調用過程教學法。將其應用于教學實踐中，有效提高了學生理解遞歸的調用和執行過程，教學取得了明顯的成效。

關鍵詞：數據結構;遞歸算法;遞歸調用;遞歸調用棧;棧幀

中圖分類號：TP311.1 ? ? 文獻標識碼：A 文章編號：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 ?引 ?言

遞歸是程序設計中一個強有力的工具，在數據結構中經常被用到。筆者曾通過把遞歸算法同時應用到后端以及前端代碼，實現了數據庫后端數據驅動到前端動態遞歸結構的網頁自動生成框架，成功解決了公司的問題。在開發過程中，要把遞歸算法與前端的AngularJS框架中的Directive以及眾多的其他前端控件融合在一起，如沒有深入了解遞歸算法的原理和調用執行過程是不可能成功的。但是，現有的教材和教學方法缺乏足夠的內容和方法去幫助學生透徹理解遞歸調用和執行的復雜過程，因此普通高校的學生不能很好地掌握該知識。

1 ?遞歸算法及其重要性

遞歸具體指一個過程或函數在其定義或說明中直接或間接調用自身的一種方法[1]。遞歸不僅是數學中的一個重要概念，也是計算機程序設計中一個強有力的工具。在如下三種情況下都要用到遞歸。其一，有很多數學函數是遞歸定義，如本文將要舉例的階乘函數;其二，有的數據結構，如二叉樹、廣義表等，由于結構本身固有的遞歸特性，則它們的操作可遞歸地描述;其三，還有一類問題，雖然問題本身沒有明顯的遞歸結構，但用遞歸求解比迭代求解簡單，如Hanoi塔問題[2]。“數據結構”是計算機專業中涉及編程的核心基礎課程，常見的數據結構介紹中，有一半左右的章節用到遞歸算法。如廣義表、樹、圖、查找、排序等。由此可以看出，遞歸相當廣泛地應用與計算機領域。

2 ?目前教學中存在的問題

由于遞歸的特點是用少量的代碼描述解題過程中的多次重復。其簡潔的代碼背后隱含了嵌套、遞歸的很多內容。例如，遞歸函數中在調用自己的代碼的操作與其下一步操作之間，從代碼來看是緊鄰的關系;但是程序實際調用和運行中，它們之間可能經歷了非常多的過程和步驟。一個遞歸函數的調用，根據調用參數的情況，可能隱含了無數次的遞歸調用。直到遞歸出口，才開始層層回溯，最后才能執行到遞歸調用操作之后的代碼。由于反復多次的調用，代碼執行的整個過程的來處和去處，很容易被混淆。但是，現有的教材主要講述遞歸模型并展示遞歸的分解和求解的簡單示意圖，沒有詳細深入地剖析調用過程，因此學生不清楚代碼執行過程，同時對為什么遞歸可能會消耗很大的內存、為什么使用遞歸要謹慎、為什么遞歸效率低沒有清晰的認識。在學習這部分內容時，尤其是在普通高校學生基礎相對不夠扎實的情況下，很少同學真正了解遞歸程序實際的運行過程，因此無法真正掌握遞歸的精髓并正確運用。

3 ?教學中如何改進

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

代碼如下：

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

}

代碼包含一個main函數，在main函數中調用函數ftrl（）。由于在ftrl（）中，代碼的第四行重復調用本函數，只是減小了參數，因此ftrl是一個遞歸函數。

3.1 ?遞歸分解和求解過程

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

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

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

3.2 ?遞歸調用棧與棧幀

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

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

圖3的第二部分是ftrl（3）被調用后棧和棧幀的情況。就是在main函數的棧幀上加上ftrl（3）的棧幀。在ftrl（3）的棧幀中，n是函數參數，3是從main函數傳過來的;pre是局部變量，目前還沒有值，需要等到ftrl（2）調用執行完成后將其返回值賦給pre。同樣，在ftrl（3）中調用ftrl（2），程序要在這里中斷并跳轉，就需要在ftrl（3）的棧幀中保存ftrl（2）的返回地址，這個地址就是把ftrl（2）的結果賦值給pre的指令的內存地址。

圖3中的第三部分是ftrl（2）被調用后棧和棧幀的情況圖。就是在ftrl（3）的棧幀上加上ftrl（2）的棧幀。在ftrl（2）的棧幀中，n是函數參數，2是在ftrl（3）中被調用時傳過來的，ftrl（2）的棧幀的其它說明與上面ftrl（3）的很相似，就不贅述。

在ftrl（2）中調用ftrl（1），添加ftrl（1）的棧幀。因為ftrl（3）和ftrl（2）都不能直接求解，所以一直都是壓棧的過程。直到ftrl（1）被ftrl（2）調用時，ftrl（1）能被直接求解，這時到了遞歸出口。這就是圖3的第四部分，棧頂是ftrl（1）的棧幀，其函數參數是1。在執行ftrl（1）時，滿足if條件，因此直接返回1。遞歸到此開始退棧。

在圖的第五部分，ftrl（1）的棧幀退出。ftrl（1）把返回值1賦給ftrl（2）的pre變量。隨后，圖的第六部分ftrl（2）退棧并把返回結果2賦值給ftrl（3）中的pre局部變量。之后，圖的第七部分ftrl（3）的棧幀退棧并把返回值6返回給main函數的局部變量b。最后，圖的第八部分main函數的棧幀退棧，main函數中輸出b的值到屏幕。可以看到，函數的局部變量越多，遞歸調用的層次越深，內存占用就越大，因為棧存在于內存空間。內存占用嚴重時，例如由于遞歸算法的錯誤導致遞歸不能結束，可能造成內存消耗殆盡導致系統崩潰。這就是要慎用遞歸的原因，也是我們要真正透徹掌握遞歸原理和調用過程的原因，在沒有真正掌握時使用很容易出錯。遞歸調用這樣不斷壓棧、退棧的過程，消耗的時間和空間資源都大，所以遞歸算法執行效率不高。

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

4 ?結 ?論

本文簡要介紹了遞歸算法以及它在計算機領域的重要性，說明了在目前普通高校“數據結構”課程遞歸算法教學中存在的不足，并提出了改進的意見。筆者將這種方法用于自己的教學實踐中，調動了學生的好奇心和潛在的求知欲，教學取得了明顯的收效。

參考文獻：

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

[2] 嚴蔚敏，吳偉民.數據結構（C語言版） [M].北京：清華大學出版社，2007.

[3] 李春葆.數據結構教程：第5版 [M].北京：清華大學出版社，2017.

[4] 牛思先.數據結構：第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] 傳智播客.數據結構與算法——C語言版 [M].北京：清華大學出版社，2016.

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

作者簡介：宋衛紅（1968—），女，漢族，云南昆明人，計算機專任教師，博士，研究方向：描述邏輯推理、知識推理、知識圖譜。