摘  要：递归是程序设计中一个强有力的工具，其在数据结构中经常被用到。但是目前普通高校学生不能真正深入理解并掌握教材中关于递归及递归算法的内容，尤其是递归调用的复杂过程。文章研究了基于代码的递归调用过程图以及递归调用栈和栈帧变化图，提出了基于这两种图的递归调用过程教学法。将其应用于教学实践中，有效提高了学生理解递归的调用和执行过程，教学取得了明显的成效。

关键词：数据结构;递归算法;递归调用;递归调用栈;栈帧

中图分类号：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—），女，汉族，云南昆明人，计算机专任教师，博士，研究方向：描述逻辑推理、知识推理、知识图谱。