内容摘要：递归算法是算法设计中常用的一种算法，运用递归算法编写的递归程序运行机理较为复杂，涉及到数据结构、操作系统、编译原理等计算机专业知识；并且递归程序的执行是一个动态的过程，关于递归算法和程序的知识可称为动态知识。用传统的语言很难描述和组织这种具有过程性的动态知识，这给学习者学习递归程序、理解递归算法带来很大的困难。计算机的出现使人们可以将现实世界的事物用一定的形式组织起来，并模拟其运行规律，本课题就是研究如何把递归算法这种过程性知识用计算机软件模拟的方式组织起来，解决动态知识的描述和组织问题。本文按软件工程的方法，从需求分析、软件设计、软件开发几个方面探讨如何用面向对象语言Visual C++及其图形用户接口设计直观的递归算法模拟软件，详细地阐述递归算法的基本原理，真实生动地再现递归程序的执行过程，从而更好地辅助学习者认识递归、学习递归并运用递归。
关键词：递归算法模拟软件动态知识
The Simulation software design and realization
of recursive algorithm
Abstract: The recursive algorithm is a commonly used algorithm in algorithm design, but the recursive program execution mechanism is complicated,which involves to expert knowledge of computer such as data structure, operating system, compiling principle; Moreover the recursive program execution is a dynamic process, It is very difficult to describe and organize this kind of procedural knowledge in traditional language, and it is difficult to learn too. Appearance of the computer make people organize this kind of dynamic knowledge by the form of courseware or cartoon, which is a good solution for description and organization of dynamic knowledge. This topic studies the way to organize this kind of procedural knowledge such as recursive algorithm by simulation software. This article, according to the method of software engineering, from demand analysis,software design to software development,studys how to use object-oriented language Visual C++ and its graphical user interface to design recursive program simulation software ,which can vividly describe the process of recursive program implementation.
Key words: Recursive algorithm Simulation software Dynamic knowledge
1.引言
一个直接或间接地调用自身的算法称为递归算法[1]，在程序设计中，使用递归算法可使程序语言简洁，结构清晰。然而，相对于非递归算法程序而言，递归程序的执行过程比较复杂。不像非递归程序直线式的执行，递归程序是自己调用自己，而且不只一次嵌套调用；递归调用还涉及到栈的出入操作，程序的局部变量（如参数等）随着调用层次的增加（入栈）或减少（出栈）不断改变，程序当前执行在哪一层？这一层上的参数是什么？这些问题给学习者理解递归算法带来困难。
传统的语言在描述这类问题上明显不足，它很难讲述清楚递归嵌套调用的整个过程及在这个过程中各变量的变化。而计算机在描述事物过程这一方面具有独特的优势，因此，可利用计算机将递归算法用软件的形式组织起来，模拟其运行过程，揭示其运行规律，从而更好地辅助学习者学习。本文就是在分析现有系统的基础上，探讨如何设计和实现这种模拟软件。
2.系统需求分析
2.1现有系统分析
对递归的研究，理论上大多从数学模型、算法复杂性、空间效率等方面探讨递归程序的运行机理，这些知识是供人们学习递归的有力材料，但这些知识都是以书籍、期刊、文章这种传统的形式——文本来组织的。对于一些形象的、可用语言描述的知识用传统的方式表达还可以，但对于较抽象的、难于用语言描述的知识，比如算法、程序运行等过程性知识，传统的方式就显得不足。计算机时代的到来，改变了传统的知识组织形式，可视化、多媒体化使得知识的表示更加形象；也改变了传统的思维方式，知识的组织更加科学。对于传统语言难以描述的过程性知识，使用计算机将其重新组织，做成动画、游戏、模拟软件等形式，丰富了知识的表达形式，使知识的组织更加科学，学习者学习起来更加容易。
当今，人们已有将递归程序做成动画、游戏等形式，供学生学习、娱乐，分析市面上关于递归程序的学习资料，大致可分为以下几类：
●文本类：在讲程序设计的书中，大多有对递归的介绍，不管是纸张式的，还是电子书籍，但用的还是文本这种传统的形式描述，这种资料学习起来效果不佳。
●动画类：这类资料利用动画技术将递归程序的执行做成动画，供学习者观看。动画技术虽然可将文本知识可视化，但其最大的缺点是用户不能有效控制。
●游戏类：利用计算机语言将一些递归问题做成游戏，比如汉诺塔游戏，这类学习资料用户可操作性强，前提是用户必须有递归这种思想。其缺点在于缺少对递归知识的介绍。
课件类：这类资料综合以上各类特点，既有静态的知识，又有动画或游戏，是最好的学习资料。但鉴于大部分课件使用Authorware、Flash甚至就是PPT制作的，虽然可将文本、动画结合在一起，但大多是简单的拼合，没有有机地结合在一起，用户的交互性比较少，可控性较差。
鉴于现有系统的存在一些问题，本课题的任务是研究一种递归算法模拟软件，它是一种软件，具有软件的一般功能，但它又不是单纯的软件，其目的是供学习者用的，是一种学习型的软件，从这个角度看，它亦是课件。
2.2待开发系统的功能需求
用Authorware 、PPT等做的课件功能是有限的，可扩充性不好，交互性也有限，不能实现高难度的交互操作。本课题将利用Visual C++的强大编程能力，开发一种图形用户界面的递归算法模拟软件。具体功能如下：
1）整合有关递归知识点，比如递归的概念、递归的时空复杂性、经典递归问题选讲。其组织形式是节点——链的超文本结构，用户可以任意选择知识点。
2) 递归算法模拟模块：分程序运行模拟、递归程序空间组织、递归结果的表示三个侧面，从不同角度模拟递归程序的运行。这个模块要求用户有控制权，系统能对用户的操作出正确的响应。
3) 递归算法运行演示模块：在这一模块中，系统有控制权，而用户可选择暂停或继续。
3.系统设计
3.1系统结构设计
根据系统的需求分析结果，递归算法模拟软件的系统结构设计结果如图1所示。
整个系统分为“概念”、“原理”、“时间”、“空间”、“演示”五个功能模块，其中概念模块下有“概念及原理”、“空间效率”、“时间效率”、“经典问题”和“递归与分治”等子模块；演示模块分四个子模块：阶乘问题、汉诺塔问题、N后问题和迷宫问题。
图1系统结构图3.2界面设计
欢迎界面的设计，如图2所示。
图2欢迎界面
单击欢迎界面进入模拟软件主程序界面，如图3所示。
图3主程序界面
主界面由工具栏和用户窗口组成，工具栏由“概念”、“原理”、“空间”、“时间”、“最小化”、“恢复”、“退出”七个按钮组成。其中概念栏左侧是树形工具条，由递归的概念和原理、递归算法的空间效率、递归算法的时间效率、经典递归问题选讲、知识扩展几大模块组成，每一模块各有下属知识。单击左侧的标题，右侧文本区显示对应的知识。左侧的知识层次还可通过单击前面的小按钮展开和隐藏。
单击演示按钮，显示汉诺塔问题、阶乘问题、N后问题、迷宫问题四个功能按钮。
图4 演示界面
单击汉诺塔问题按钮，进入模拟运行界面，如图5所示。
图5模拟运行界面
此界面由工具栏和四个视图组成。左上为程序执行视图，随着程序的执行，模拟C编译器中程序执行的式样，程序执行到哪一行，相应行显示绿色背景条；左下为栈视图，随着程序的递归执行进行相应的入栈和出栈，并显示各参数值的变化。其中Addr为递归调用的入口地址，n为递归调用的层次，x、y、z为传入参数，随着调用层次的不同而改变。当递归调用一次时，Addr、n、x、y、z值入栈，反之，当递归调用返回时出栈；右上视图显示程序执行的结果，对于汉诺塔问题，即为移盘子的操作步骤；右下视图为程序执行的可视化结果，比如汉诺塔问题的盘子移动操作。
工具栏由“设置”、“切换”、“帮助”、“恢复”、“执行”、“暂停”、“跳过”、“跟踪”、“最小化”、“最大化”、“返回”等十一个功能按钮组成。具体功能如下：
●“设置”按钮用来设置本程序的全局参数，比如汉诺塔问题的盘子个数，程序自动执行的速度等参数。
●“切换”按钮用来在四个视图之间切换，这里只切换到左上视图，即左上视图最大化。
左上视图除了模拟C编译器程序的执行外，还可直观地模拟递归程序的运行。当递归程序深入一层，就产生一个新的递归程序块，程序又从新的程序开头执行，而上一层的程序停留在调用位置，当其调用子程序返回时，删除子程序块，程序又从主程序中止处开始执行。这样避免了只在一个程序中显示程序的过程，仍然看不清是被谁调用的，调用层次是多少，调用返回到哪儿的弊病。更进一步直观的再现递归程序的执行过程。
●“运行”按钮实现了程序的自动执行，即自动演示功能。按暂停则程序停止运行，再按运行则程序继续执行。
●“跟踪”按钮实现编译器中的跟踪执行功能，并且控制四个视图的同步运行，即主程序的执行，栈的出入，中间结果的输出及结果的可视化展示。每按一下，程序执行一步（左上），每进入一层递归调用，相应数据入栈，每次递归调用返回，则出栈（左下），每当程序运行到move操作，右上输出结果，右下则模拟执行。
●“跳过”按钮实现编译器中的跳过执行功能，与跟踪功能不同的是，每次递归调用，单步跟踪就进入下一层程序，一步一步执行，而跳过功能一次性执行该递归调用，并返回本程序，执行下一步操作。跳过功能可忽略中间调用的过程，直接产生此次调用结果，对理解递归的执行很有益处。递归的思想本来就是将一个问题抽象为可递归的子结构，通过若干层递归调用，得到结果，跳过功能忽略以下各层的调用细节，直接得出本层调用结果，相当于把问题分解，是一种分治的思想；知道了本层调用结果，若想更进一步理解如何得到这个结果，再利用跟踪功能，进行跟踪。这样一步步分解，对透彻理解递归的运行机制大有用处。
●“恢复”按钮用来恢复软件的默认设置或者初始状态。
●“帮助”按钮弹出一个对话框，简要介绍本软件的使用方法。
●“最小化”按钮用来进行任务切换，单击它可最小化本程序，切换到其他windows程序。
●“返回”按钮用来返回到主界面。
3.3设计用例实现方案
针对系统功能模型的分析，设计具体的用例对象，如用户、界面、窗口等，用顺序图描述各对象之间动态的交互关系，着重表现对象间消息传递的顺序。如图6所示。
图6 软件用例的顺序图
3.4系统类设计
3.4.1软件类属关系图
在用例实现方案的基础上，对每个用例设计类及其方法，得到详细的软件类关系图。如图7所示，带箭头的为消息。
图7 类属关系图
3.4.2各类及其功能
●Cstep1App：应用程序类，基类为CWinApp，由其负责程序的初始化，并定义程序的唯一对象myApp。
●CmyFaceDlg：进入界面的对话框类，基类为CDialog。由其定义进入对话框模板资源及其上的响应事件，对应的方法为OnJinru()。
●CshowDlg：演示界面的对话框类，基类为CDialog。在演示界面上有四个功能按钮，其中本软件只是实现汉诺塔问题，对应方法为OnHan()。
●CSizingControlBar :自定义工具条类，基类为CControlBar，负责主程序界面中左侧树形工具条的定义和维护，处理相应的鼠标事件，如鼠标按下、释放、工具条大小的改变。
●MyTree ：树形节点类，基类为CTreeCtrl。
●Mybar：树形工具条类，基类为 CSizingControlBar，在此类中定义MyTree 类对象 m_TreeCtrl，并向其中插入节点及子节点。
●CMainFrame ：主框架窗口类，基类为 CFrameWnd，负责主程序界面的定义和维护。如工具条的导入，其他工具的定义，此处为mybar类m_CtrlBar，及程序的退出方法OnButtonExit()。
●CCTreeControlBarView：视图类，基类为CView。是与框架窗口类CMainFrame 对应的视图类，负责主界面的显示，本例中用来显示与m_CtrlBar 树形工具条每个节点对应的文本。本类实现的方法有：OnDraw(CDC* pDC)负责显示树形工具条每个节点对应的文本；OnButtonGn()返回概念窗口；OnButtonShow()打开演示界面对话框；OnButtonMini()最小化窗口； OnInitialUpdate()当鼠标在左侧树形工具条的节点间转换时更新右侧对应文本的显示。
●CMySplitter ：本软件的第二个框架窗口类，基类为CFrameWnd，负责模拟运行界面的定义和维护。本类定义的CSplitterWnd m_wndSplitter对象实现模拟运行界面的四分窗口，即四个视图：左上、左下、右上、右下；OnTextShow()事件实现四分窗口和左上视图窗口之间的切换；窗口的最小化和返回主界面功能也在本类中实现。
●CTexView ：左上程序视图类，基类为CView。左上视图是本窗口的主视图，控制并实现四个视图的同步。本视图与文档类CStep1Doc交换数据，通过文档更新将数据传给其他视图。本类方法有：OnSetn()打开设置界面并把用户设置的参数存储；OnTraceinto()实现递归程序的跟踪调试；OnStepover()实现递归程序跳过运行；OnRun()实现递归程序的自动演示执行；OnStop()与OnRun()一起配合演示的暂停与继续；OnRestore()用于恢复默认初始状态。
●CStack 、CPlate 、CResult ：基类都为CView，分别实现栈的出入，盘子的移动和结果的输出。
●CStep1Doc：文档类，基类为CDocument。该类是本软件各视图的公共文档类，负责定义、存储各视图的公共数据。如递归调用的层次、递归入出口、当前参数值及历史参数值表。
4.系统实现
4.1Visual C++的文档视图结构和消息映射机制
4.1.1Visua C++的文档/视图机制
1）文档与视图
在Visual C＋＋文档/视图结构里，文档是一个应用程序数据基本元素的集合，它构成应用程序所使用的数据单元，提供了管理和维护数据的手段。视图是数据的用户窗口，为用户提供了文档的可视的数据显示，它把文档的部分或全部内容在窗口中显示出来。视图给用户提供了一个与文档中的数据交互的界面，它把用户的输入转化为对文档中数据的操作[2]。一个文档可以有多个不同的视图。图8说明了文档及其视图之间的关系。
图8 文档视图关系图
2）框架窗口
Windows应用程序都是以窗口的形式表现，所以在应用程序中对窗口的维护成为一项重要工作，诸如创建窗口、显示窗口、必要时重画窗口内容、关闭窗口等。这些工作就由框架窗口来完成。
对于SDI应用程序，框架窗口就是程序的主窗口，称为主框架窗口；对于MDI应用程序，框架窗口又分为主框架窗口和子框架窗口，其中主框架窗口是程序的主窗口，子框架窗口是主窗口下的子窗口。视图在框架窗口中显示，占据框架窗口的客户区。当框架窗口关闭时，在其中的视图也被自动删除。
3）文档模板
文档模板负责创建文档、视图和框架窗口。一个应用程序对象可以管理一个或多个文档模板，每个文档模板用于创建和管理一个或多个同种类型的文档。应用程序中的每一种文档，都必需有一种文档模板和它相对应。
文档模板定义了文档、视图和框架窗口这三个类的关系。通过文档模板，我们可以知道在创建或打开一个文档时，需要用什么样的视图、框架窗口来显示它。
4.1.2Visua C++的消息映射机制
Windows应用程序是消息驱动的，Windows消息包括两大类：标准的Windows 消息和命令消息。标准的Windows消息是程序的启动或退出、窗口的创建或关闭、窗口移动、窗口大小改变等事件引发的消息，命令消息是由于用户发出的如菜单命令、工具按钮命令等引发的消息，标准的Windows消息必须由窗口类的对象，即直接或间接地由CWnd类或其派生类的对象进行处理，而命令消息可由APP类、主框架类、视类和文档类来处理[2]。
1）消息映射
MFC应用程序采用消息映射的机制对消息进行响应处理。消息映射机制就是一张消息及其处理函数一一对应表以及分析处理这张表的程序。
首先在类定义中声明DECLARE_MESSAGE_MAP()，并在类的实现文件中加入消息映射表：
BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)
//{{AFX_MSG_MAP(CMainFrame)
//消息映射表
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
在类中定义消息处理函数，并在类实现文件中实现其代码，然后在消息映射表中加入相应消息映射入口项，就完成了一个消息映射。
DECLARE_MESSAGE_MAP、BEGIN_MESSAGE_MAP、END_MESSAGE_MAP和那些消息映射宏构成了消息映射机制的基础。
2）消息循环
在文档、视图和框架被创建后，消息循环就开始了。其消息传递机制是将某种类型的消息按一定的顺序从一个对象传到另一个对象，直到该消息被某个消息处理函数处理，否则将消息传递到DefWindowProc进行默认的处理。
窗口函数在传递命令消息时，会按照“视类—>文档类—>主框架类—>APP 类”的顺序来传递，直至找到一个消息处理函数为止，如果中间某个类有一个相应的消息处理函数，那么就调用该函数，然后返回，不再继续向下传递，这也就是说，如果视图类和文档类都处理了同一个命令消息，那么文档类的处理函数不会被调用。SDI程序的消息传递过程[3]如图9所示。
图9 SDI程序的消息传递过程
图10展示了Windows应用程序的流程和消息循环及处理机制。
图10 Windows消息处理流程
4.2界面实现
4.2.1欢迎界面的实现
欢迎界面是整个程序的入口，负责显示软件的名称、制作单位和个人信息，在VC++中只需要用一个对话框来表示，因此，需要做两方面的事情：制作对话框资源和定义与之相应的对话框类。
1）制作对话框资源
第一步：在资源面板上选择Dialog项，右击选择Insert Dialog，插入对话框；
第二步：在弹出的对话框面板中，插入三个静态文本框，并分别在其属性的标题项中输入要显示的文字；
第三步：在资源面板上选择Bitmap项，右击选择Import，在弹出的面板中选择要导入的位图；
第四步：在对话框中插入图像控件，并在其属性的图像选项中选择要显示的图像名称。
2）定义对话框类
对话框类负责对话框资源的管理，除了显示外，在对话框类中还需要定义数据交换支持并把控件同对话框中相应的消息处理函数联系起来[4]。数据交换支持是为了实现对话框和成员变量之间的数据交换；消息处理函数是为了处理用户的交互请求，如鼠标事件、键盘事件等。
欢迎界面的实现效果如图11所示。
图11欢迎界面实现图
4.2.2主界面的实现
主界面包括两个工具条和一个显示窗口，其中窗口上方的工具条的作用如同菜单命令，可以实现窗口最大化、最小化、关闭以及同一个窗口中不同内容之间的切换。其制作过程如下：
第一步：在资源面板上选择Toolbar项，右击选择Insert Toolbar，插入工具条；
第二步：利用VC的位图编辑工具制作各功能按钮；
第三步：在主框架类中添加导入工具条代码；
第四步：给各按钮添加响应事件。
窗口左边是树形条，由一个个节点组成，每个节点还可有子节点；每一个叶子节点与一个知识点对应，由此组成知识点的层次结构。单击左侧的树形节点，右侧的窗口则显示相应的知识点。其制作过程除了自定义控制条外，同标准工具条。
主界面的实现效果如图12所示。
图12主界面实现图
4.2.3演示界面的实现
演示界面实质也是一个对话框，与欢迎界面不同的是，欢迎界面的对话框是模态对话框，而演示界面是非模态对话框。
模态对话框是指在程序继续运行之前需要用户对该对话框作出响应，也就是说，在关闭这一对话框之前不能处理对话框以外的事情；非模态对话框是指对话框随时可用，并且允许应用程序处理对话框以外的用户事件[4]。
非模态对话框的实现也和模态对话框一样，需要制作对话框资源和定义相应的对话框类，他们的不同之处在于创建对话框对象上。模态对话框的创建只需要创建一个对话框对象，然后调用DoModal()事件；而非模态对话框的创建需要定义一个对话框类的指针，然后调用Create()事件动态的创建对话框对象。
为了显示非模态对话框，还需要定义打开非模态对话框的方法，这里是给主界面工具条的演示按钮添加打开非模态对话框事件：
选择资源面板中主界面的工具条，单击演示按钮，选择查看菜单下的建立类向导，在弹出的面板中选择演示按钮，并在类选项中选择对应的视图类，在事件选项中选择Command，双击它即为演示按钮添加了响应事件，然后在其中写入相应的代码。
在主界面中，单击演示按钮，弹出演示界面。如图13所示。
图13演示界面实现图
4.2.4模拟运行界面的实现
1）模拟运行界面
模拟运行界面由四个视图组成，左上视图负责递归程序的运行模拟，左下视图负责递归栈的出入模拟，右上视图负责程序运行结果的输出，右下视图在汉诺塔问题中负责显示移盘子的操作过程。
四分窗口是由切分条组件来实现的。切分条组件把窗口分成若干个部分，每个部分称为一个切分块，每个切分块负责维护一个视图类，因此实现了一个窗口显示多个视图的功能。
此外，模拟运行界面也带有工具条，其制作方法同主界面；为了界面的简洁美观，隐藏了标题栏和菜单栏，实现了窗口的最大化。
模拟运行界面的实现如图14所示。
图14模拟运行界面实现图
2）视图切换
视图切换负责在四分视图和单个视图之间的切换，其实现只需要移动切分条。比如要切换到左上视图，就把横向切分条移到最低端，把纵向切分条移到最右端。而要再切换到四分视图，只需要将它们都移到中间。
程序运行，单击切换按钮，切换到左上视图，如图15所示。再次单击切换
按钮，则又切换到四分视图。
图15左上视图
4.3模块算法
4.3.1多文档模板的使用
首先在应用程序初始化时定义文档模板：
BOOL CStep1App::InitInstance()
{
pDocTemplate1= new CSingleDocTemplate(
IDR_MAINFRAME,
RUNTIME_CLASS(CStep1Doc),
RUNTIME_CLASS(CMainFrame),
RUNTIME_CLASS(CCTreeControlBarView));
pDocTemplate2= new CSingleDocTemplate(
IDR_MENU1,
RUNTIME_CLASS(CStep1Doc),
RUNTIME_CLASS(CMySplitter),
RUNTIME_CLASS(CTexView));
}
在应用程序初始化时定义了两个文档模板pDocTemplate1 ，pDocTemplate2。pDocTemplate1负责主程序框架CmainFrame、主文档CStep1Doc、主视图CCTreeControlBarView三者的统一管理，实现主界面的功能。pDocTemplate2负责框架CmySplitter、文档CStep1Doc和视图CtexView的统一管理，实现四分视图模拟运行界面的功能。
然后定义打开文档的方法:
CDocument * CStep1App::OpenShow1DocumentFile(LPCTSTR lpszFileName) {
if(pDocTemplate1)
return pDocTemplate1-> OpenDocumentFile(lpszFileName);
else
return NULL;
}
对pDocTemplate1作同样处理。
在需要打开文档模板的地方调用OpenShow1DocumentFile即可。
CStep1App *myapp=(CStep1App*)AfxGetApp();
myapp->OpenShow1DocumentFile(NULL);
myapp->m_pMainWnd->ShowWindow(SW_SHOWMAXIMIZED );
myapp->m_pMainWnd->UpdateWindow();
4.3.2递归程序模拟运行算法（以汉诺塔问题为例）
1）递归程序的实现
递归程序包括程序调用和返回处理两部分。
程序调用可以分解成以下三步实现[5]：
(1)保存断点信息：主要有主程序的局部变量、返回地址等，等调用返回后
可再利用；
(2)分配给调用程序的数据区：将主程序的参数传给子程序，并开辟子程序
局部变量等必要的存储区；
(3)转移到被调程序的入口。
递归调用结束后，需要返回到调用程序，也分三步：
(1)保存结果：指被调程序要传递给调用程序的信息，如计算结果等；
(2)释放被调程序的数据区；
(3)转移到调用过程的断点，从上次中断处继续执行。
2）汉诺塔问题模型
汉诺塔问题：设有ABC三个塔座，初始时，A塔上有n个圆盘，这些圆盘
自下而上,由大到小叠在一起，并依次编号为1，2，……N，现要求将塔座A上
的这一叠圆盘移到塔座C上，并仍按同样顺序叠置，在移动圆盘时须遵守以下规
则[5]：
规则1：每次只能移动一个圆盘；
规则2：始终是将小圆盘放在大圆盘之上。
3）解决汉诺塔问题的思路
把N个盘子从A塔移到C塔，分为三个步骤来完成：
第一步：借助C塔，将A塔上的N-1个盘子移动到B塔上；
第二步：把A塔上剩下的一个盘子移到C塔上；
第三步：借助A塔，把N-1个盘子从B塔上移到C塔上。
用C语言程序表示即为：
0:void hanoi(int n,char x,char y,char z)
1:{ if(n==1)
2: move(1,x,z);
3: else 4: { hanoi(n-1,x,z,y);
5: move(n,x,z);
6: hanoi(n-1,y,x,z);
7: } 8:}
4）递归程序模拟的实现
递归程序的模拟并不需要按实际递归的执行过程来运行递归程序，设想，如
果能把递归程序转换为非递归程序，那么在应用程序中就可用非递归的程序来模
拟递归程序。
在递归转换过程中需要栈这种数据结构，递归程序转化为非递归程序的实质
是将系统管理的递归工作栈改为自己管理[5]。通过对递归的实现的认识,可得如
下转化规则[5]：
（1)设置一个栈,并且开始时将其置空；
（2)在子程序入口处设置一个标号；
（3)对子程序中的每一次递归调用,按如下步骤执行：
●保留现场：开辟栈顶存储空间,用于保存返回地址和调用层中的形参和
局部变量的值；
●准备数据：为被调子程序准备数据,即计算实参数的值，并赋给对应的
形参；
●转子程序：执行子程序；
●回传数据：将执行结果保存到回传变量中；
●恢复现场：从栈顶取出返回地址及各变量,形参的值,并退栈；
●返主程序。
（4）执行后续语句。
具体算法如下：
首先，在文档类CStep1Doc中定义的供各视图共享的数据：
char * textbuf[9];// textbuf[9]为9行递归调用的程序
int n,N; //N 是盘子个数，n是当前层上的盘子数
int speed; //程序自动执行的速度
int addr; // addr递归调用的断点，即程序进入下一层递归的入口
地址和递归调用完毕后的返回地地址。
char x,y,z; //当前层上的三个塔座
int ADDR[5];//这是地址栈，存储各层递归调用的断点，因本例数据量较小，
为了便于理解，用数组表示
char X[5],Y[5],Z[5];//这是塔号栈，存储各层递归程序的xyz所代表的塔
座号
以下是程序执行的控制按钮单步跟踪的实现算法：
程序每执行一次，按如下步骤重复，直至栈空为止：
S：定义文档指针；
CStep1Doc* pDoc = GetDocument(); //子程序入口
1：如果t_flag=0（初始状态下或递归调用进入时，程序停在第0行）,致栈标记为1，表示入栈,并将相应的数据入栈；
if(t_flag==0)
{
pDoc->initflag=1; //表示此时为入栈操作；
pDoc->ADDR[pDoc->N-pDoc->n]=pDoc->addr; //当前数据入栈
pDoc->X[pDoc->N-pDoc->n]=pDoc->x;
pDoc->Y[pDoc->N-pDoc->n]=pDoc->y;
pDoc->Z[pDoc->N-pDoc->n]=pDoc->z;
pDoc->NS[pDoc->N-pDoc->n]=pDoc->n;
t_flag=1;// 程序转第1行
}
2：如果t_flag=1，这时有两种情况：
如果pDoc->n=1，表示这层只有一个盘子，这时只需将剩下的一个盘子从X 塔座移到Z塔座，然后返回，已达递归最大层数，不再递归，故程序转第二行；
if(t_flag==1&&pDoc->n==1)
t_flag=2;
如果pDoc->n!=1表示还未到最大层数，需继续递归，故程序转第四行。
if(t_flag==1&&pDoc->n!=1)
t_flag=4;
3: 如果t_flag=2,则直接跳到子程序结尾；
if(t_flag==2)
t_flag=8;
4：如果t_flag=4，则进入子程序；
//首先保存入口地址，当前地址入栈
if(t_flag==4)
{
top=top+1;
stack[top]=t_flag;
pDoc->n=pDoc->n-1; //递归层次减一
//为子程序准备数据，即计算子程序参数值，这里是交换y z