递归执行过程中进出栈的动态演示在VB教学中的应用

郭亚庆

（十堰职业技术学院电子工程系，湖北十堰442000）

在程序设计中，递归算法一直是教学的难点，在现阶段高职教学中，传统的告知式教学还占有很大的比例。为适应学生的思维结构，帮助学生构建他们能理解的知识，从而顺利理解复杂的数学问题，特制作汉诺塔进出栈的动态演示程序，应用到VB教学中，从而把复杂的教学问题变为直观，生动的动画教学，以提高教学效果。

一、递归算法

递归算法是一种直接或者间接地调用自身的算法。它的实质是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解［1］。

递归算法清晰简练、易读，但要讲清楚递归的执行过程，让学生能够掌握递归的实质以及揭示递归与堆栈的内在联系，却不是一件很容易的事。

堆栈（Stack）是一种比较重要的线性数据结构，它的插入、删除操作是固定在一端进行的，这一端称为栈顶（top），另一端称为栈底（bottom），向栈中插入数据的操作称为压栈（Push），从栈中删除数据称为弹出（Pop）。在计算机中正是由于有了堆栈这种数据结构，才使递归算法得以实现。

二、递归过程执行分析

下面我们以Hanoi塔问题为例，相传在印度，有一个梵塔，塔内有三根柱子A、B、C，A柱上有64个盘子，盘子大小不等，大的在下，小的在上，有一个和尚想把这64个盘子从A柱移到C柱，但每次只能允许移动一个盘子，并且在移动过程中，要求3个柱上的盘子始终保持大盘在下，小盘在上。

我们将三根柱子分别标号为A、B、C，目的是要将n个盘子从A柱子移动到C柱子。该问题的算法如下：第一步将A柱子上n－1个盘子借助C柱子移动到B柱子上；第二步 将A柱子上剩余的第n个盘子移动到C柱子上；第三步 将B柱子上的n－1个盘子借助A柱子移动到C柱子上［2］。

对于第一步和第三步，我们又可以利用类似的方法继续将其求解过程设计为一个规模为n－1的Hanoi塔递归算法。

递归过程的实质是循环执行递归过程中递归调用语句前的几个语句，每次执行递归调用语句时将返回地址及实参的值进栈保留，调用时注意形参与实参的结合。若是变参不在重新分配内存单元，若是值参（如本例中的N，A，B，C）每调用一次都给N，A，B，C变量重新分配内存单元，登记该变量在本层的实际值，当我们单击按钮2时，便开始调用递归程序，实参N（设N＝3），1，2，3分别传送给形参N，A，B，C。这时返回地址FH及N，A，B，C对应的实参值进栈，当N不为1时，用30语句hanoi N－1，A，C，B（实际用2，1，3，2）再调用，N又不为1，再用30语句hanoi N－1，A，C，B（实际用1，1，2，3）调用，直到满足N＝1时，则执行20语句：A－＞C，这时对初学者来说往往找不到A，C的实际值，而无法写出源柱和目标柱。即使执行完20语句后，又因找不到返回地址而感到茫然，靠一步步推算，写出进出栈参数及返回地址，即费时又易出错，当N值大于3时，推算更为困难。为此本人开发了汉诺塔问题进出栈动态演示程序，它生动而直观显示了进出栈参数及返回地址，记录了栈内参数的变化，根据栈顶的参数，很方便地写出“A－＞C”。从而加深了学生对递归过程执行的理解。

三、进出栈动态演示程序的设计

1.界面设计

在屏幕左半部上画出栈图，栈图上方有五个文本框，标示为ADR（返回地址）N，A，B，C以表示进栈的参数。在栈底左侧画出栈指针，栈指针是先作一个框架，然后在框架内放入一个标签框，一个文本框和箭头，其中文本框是用于存放栈顶的地址，初始指向栈底。屏幕的右半部上方有一个文本框用于提示执行情况。屏幕的右半部的中间为输出结果，下部为三个按钮。

2.初始化

先输入园盘个数N，由于屏幕关系，园盘个数仅限于3和4，然后根据园盘个数在屏幕的右半部产生7或15个标签框用于显示输出结果，再产生8行5列的文本框填入栈图作为栈空间，并将它们的Visible属性设为False。

3.进出栈时间的安排

在什么时候进栈，什么时候出栈这是进出栈的动态演示程序设计的关键，我们知道每当调用子程序时，就必须将返回地址及相应参数压栈，为此我们在上述算法的三处插入了调用进栈子程序，并且用窗体级变量X来统计栈内的项数，每当进栈X就加1，每当退栈X就减1。进而分析可知，一旦满足条件N＝1时，就会执行20显示输出结果，执行完20语句之后，就会退出块IF语句，而执行60END SUB语句，这时就从栈顶弹出一项。因而将退栈子程序插入在60语句之前。另外为正确显示输出结果，用变量T来控制LAB（T）.Caption的下标，因而在20与40语句之前插入T＝T＋1语句。改进后的算法如下。

4.进栈与出栈子程序的设计

（1）进栈子程序：栈空间是用TXTNEW的二维数组表示，它是8行5列，每个元素的类型为TEXTBOX，一行存放一次进栈的所有参数，它们分别是返回地址和N，A，B，C。进栈子程序JZ有6个形参，其中形参X为地址传递，用来控制TXTNEW二维数组的行下标，以统计栈内的项数，每当调用进栈子程序X就加1。其余5个形参分别对应返回地址和N，A，B，C，进栈子程序是先将栈指针上移，接着将栈指针内存放的栈顶地址减1，然后将返回地址和N，A，B，C这些参数存入二维数组TXTNEW的X行各列中，并显示该行，以表示进栈。

（2）退栈子程序：它有一个形参X用来控制TXTNEW二维数组的行下标，将该行各列的Visible属性设为FALSE，接着栈指针下移，然后将栈指针内存放的栈顶地址加1，每当调用退栈子程序X就减1。

附进出栈子程序如下：

［1］刘瑞新.VISUAL BASIC程序设计教程［M］.北京：电子工业出版社，2011：162.

［2］谭浩强.C程序设计［M］.北京：清华大学出版社，2010：118－119.