基于复杂递归类问题的可重用程序模板研究

摘要：构建复杂递归类问题的可重用程序模板主要是为了提高学习者分析和解决类似问题的能力。文章分析了构建可重用程序模板的理由及其设计思想，并且深入地研究了复杂递归类问题的非递归算法，实现了部分复杂递归类问题的可重用程序模板；在求解同类型问题时，只需向可重用程序模板输入问题的相应参数，就可获得该类问题的实例，并且通过此模板自动推理产生程序设计的全过程。文章实现了既有问题又有解答的无限题库，为生成无限题库提供了技术支持和理论依据。

关键词：递归问题；可重用程序模板；自动推理；软件重用

0　引言

使用递归方法设计程序会使很多复杂问题变得简单和通用。递归是程序设计中的一个强有力的工具。对于一些本身没有明显递归结构的问题也可以利用递归技术设计出简单易懂的算法程序，但其难度相应要大许多。利用递归方法编写出来的程序，结构简练、清晰，可读性强，而且它的正确性容易得到证明。正是由于它以简洁、抽象的语句解决了复杂的问题，而使得初学者感到递归程序深不可测，递归程序的设计更是望尘莫及。

在程序设计中，程序的可读性与程序的执行效率往往是互相制约的。递归算法只需要写出问题的分解形式和组合答案的方法，至于如何递归地求解各个子问题则由系统帮助解决；而递推算法常以循环的形式出现，编写程序时必须明确写出循环内的每一步是如何实现的。另外，对于复杂递归问题的求解需要复杂的数据结构和控制方法，这使得初学者难以理解复杂递归问题的非递归实现，更不用说复杂递归问题的非递归实现的推导和证明。

为此，本文设计了一个能解决部分复杂递归类问题的可重用程序模板并在系统中实现了自动推理，其中利用了PAR方法的解题步骤形式化地推导程序，清晰地阐述了程序设计的全过程。这不但可以帮助初学者有效地理解和掌握递归算法的非递归实现，而且也可以提高他们设计算法和揭示事物本质特征和规律的能力。

1　设计思想

复杂递归类问题的可重用程序模板的构建主要是利用了软件重用技术和事物相似性原理，其基本思想是：从一组类似的事物中抽象出一种框架型的模板，任何一个类似的事物都可作为以模板为超类派生的类型的实例Ⅲ。若能用一个形式模型来刻划问题的本质，那将是十分有益的事，一旦将问题形式化，就可以依据这个模型对问题进行求解。

递归问题作为一类特殊问题，本文对该类问题的非递归算法作了大量深入的研究并寻找这些算法的共同特征，发现有些问题的求解方式有很多相似之处。对于一些复杂的递归类问题(如树的遍历、图的深度优先遍历、快速排序等)，常用的方法是将问题分划为三个部分：已处理完成部分(用序列或集合x表示)，当前正在处理的部分和尚未及时得到处理的部分(用栈s保存)。正是基于这种相似之处，借鉴泛型程序设计思想，构造了复杂递归类问题可重用程序模板。

2　可重用程序模板

在数据结构中，对于树是采用递归形式定义的。实际上树和递归有着很紧密的联系，递归问题的结构一般是某一种形式的树状结构。递归问题从大到小的分解和树状结构从整体到局部的分解都是类似的。递归的逐层深入和返回也就是树状结构的穿线过程。递归的第一次调用就是树状结构的根结点；以后的逐层调用就对应于树状结构每一层展开的子结点；递归调用的结束(也就是递归的终值)就对应于树的叶子结点；并且在一个递归过程中往往存在多次的选择调用关系，于是就形成了树的分支。所以对应递归问题的调用关系就可以将其转化为树状结构，递归的实现可以转化成树的遍历。并且充分运用树状结构局部与整体的自相似将可以对递归问题的每一步进行充分的分解，使其复杂的嵌套过程变得层次清晰、关系明了。

有些问题本身具有树状形式的数据结构，例如二叉树、广义表、图等，这些问题的求解一般是以树的遍历为基础，在遍历的基础上综合求出问题的解。在此，我们采用三种遍历树的方法实现对复杂递归类问题的划分：前序，中序，后序。

前序：

Oper(Q(T))=Oper(tQ(T.I)Q(T.r))

中序：

Oper(Q(T))=Oper(Q(T.I)tQ(T.r))

后序：

Oper(Q(T))=Oper(Q(T)Q(T.r)t)

其中T表示要进行操作的数据(二叉树、数组、图)，Oper表示对原数据结构进行变换的操作，为可选项。当选择Oper项，则Q(T)表示为allnodes(T)，它表示T中所有元素或标识构成