递归与树型结构


递归与树型结构 Ξ 晏建学  王云秋 (云南财贸学院基础部 ,昆明 ,650221) 摘  要  利用树型结构本身就是一种递归定义的特点 ,引入树型结构对递归问题进行分析. 关键词  递归 ;  层次 ;  树型结构 ;  二叉树 【中图分类号】O22112    【文献标识码】A    【文章编号】1005 —7188(2002) 03 - 0176 - 03   递归作为人们熟悉而又普遍的问题 ,常常因其 复杂的嵌套关系而很难被正确理解和真正把握. 而 树作为一种常见的数据结构 ,本身就具有递归的特 性 ,同时又具有明晰的层次结构 ,易于分析和掌握. 本文利用树型结构本身就是一种递归定义的特点 , 引入树型结构对递归问题进行分析. 1  递归的产生 递归的产生原因很多 ,大致可以分为以下几方 面 :其一 ,很多数学问题不能用初等函数直接表示 , 但可以用递归定义的形式间接表示. 如 Ackerman 函 数. 其二 ,从程序设计的角度来看 ,函数或过程调用 它本身 ,就形成了递归. 还有一些问题 ,虽然问题本 身没有明显的递归结构 ,但可以用递归来求解 ,并且 更为简便. 其三 ,从数据结构的角度来看 ,有些数据结构本 身就具有递归的特性 ,它们的操作自然需用递归来 描述. 其四 ,世界本质上是非线性的 ,并且在非线性科 学中已经揭示出非线性现象的三大普适性 :孤立子、 混沌和分形 ,已成为非线性科学的三大理论前沿. 其 中分形几何研究的几何图形是不规整的、粗糙的、不 可微分的. 它无法用传统的数学方法来描述 ,但分形 具有一个重要的特点 ,即局部与整体的自相似性 ,并 且表现为无穷嵌套或无穷自相似. 因此可以用递归 或迭代的方法来描述并生成它. 由此看来 ,递归不仅在数学、程序设计、数据结 构甚至现实世界中都具有重要意义 ,而这些都归结 于递归的特点 ,在于有可能用有限的语句来定义对 象的无限集合 ,即使用有穷的递归定义可以描述无 穷多次计算 ,尽管该定义不明显地包含重复运算. 2  递归的自身局限 目前 ,科学研究已普遍使用计算机来进行各种 问题的分析和解决 ,而递归又被计算机程序设计广 泛运用 ,其地位日显重要 ,但递归本身又具有其自身 不可克服的缺陷 :(1) 从程序设计角度来看 ,递归实 际上是多个过程的嵌套调用 ,且形成了一种不明显 的层次关系. 每一层次都需要相应的空间进行存储 , 所以需要对相应的存储空间大小作分析 ,即对层次 进行分析.(2) 对于递归问题 ,运用传统的“绕圈子” 分析方式很难对其整个执行过程进行深入透彻的理 解和分析. 为了深入地理解和分析递归的层次和运 行状况 ,笔者运用层次分析方法并引入层次模型对 其进行定性、定量分析. 3  递归与树型结构的紧密联系及相互转化 递归是一种逐层深入又逐层返回反复循环的层 次调用关系 ,并且其自身就存在一种选择关系 ,继续 调用或者跳出循环调用 ,就形成了一种分支结构. 而 树是以分支关系定义的层次结构 ,因而递归的调用 过程中实际上已经隐含了一棵树. 因此 ,树型结构和 递归运行中层次与分支是完全一致的. 显然可以将 递归问题转化成树型结构 ,利用树型结构来分析递 归的层次和运行状况. 另外 ,递归问题从大到小的分解和树型结构从 整体到局部的分解都是类似的. 递归的逐层深入和 返回也就是树型结构的穿线过程. 递归的第一次调 用就是树型结构的根结点 ;以后的逐层调用对应于 树型结构每一层展开的子结点 ;递归调用的结束(也 671 Ξ 收稿日期 :2002 - 03 - 06 作者简介 :晏建学 (1963~),男 ,云南人 ,高级实验师. 主要从事数学与计算机交叉应用研究. 第 11 卷第 3 期 2002 年 7 月    云南民族学院学报 (自然科学版) Journal of Yunnan University for Nationalities(Natural Sciences Edition) Vol. 11 ,NO. 3 July. 2002 就是递归的终值) 就对应于树的叶子结点 ,并且在一 个递归过程中往往存在多次的选择调用关系就形成 了树的分支 ,所以对应递归问题的调用关系就可以 将其转化为树型结构 ,递归的实现可以转化成树的 遍历 ,使其复杂的嵌套过程变得层次清晰、关系明 了. 4  实例分析 为了更加透彻的说明递归和树型结构 (尤其是 二叉树) 的转化及其对递归问题进行分析的优越性 , 笔者以经典的 Hanoi 塔问题为例对其作较为细致的 分析如下 : 假设有三根杆 a、b、c 和 n 个大小互异的盘片 , 这些盘片可以串杆而堆放而成塔. 设 n 个盘片最初 按尺寸递减的次序堆放在 a 杆上 ,任务是将这 n 个 盘片从 a 杆移到 c 杆 ,保持原来的堆放次序 ,并且需 在下面的限制条件下完成 : ①每次只准严格地将一个盘片从一根杆移到另 一根杆 ; ②任一盘片不得放到比它小的盘片的上面 ; ③b 杆可用作辅助存储. 411  PASCAL 过程 PROCEDURE  h(n :integer ;x ,y ,z :char); BEGIN  IF  n = 1  THEN  move (x ,1 ,z)     ELSE   BEGIN  h(n - 1 ,x ,z ,y);             move (x ,n ,z);             h(n - 1 ,y ,x ,z)         END; END; 412  二叉树分析方法(图 1) 413  正确的移动次序(见表 1) 414  递归与二叉树的转化 第一次递归调用为 h (n ,x ,y ,z) 即为树的根结 点 ,然后递归问题的每一次深入均是调用语句 h (n - 1 ,x ,z ,y),因而对应于二叉树的左结点均是该语 句执行的结果. 同样 ,每一次递归调用之后均返回并 再调用语句 h(n - 1 ,y ,x ,z),该语句执行的结果即为 二叉树的右结点 ,递归的执行过程也就是二叉树的 形成过程. 递归的执行 ,就是对二叉树进行遍历的过程 ,本 例是一个典型的中序遍历. 每一次调用均有一次行 为结果 move (x ,n ,z). 对其树型结构进行中序遍历就 得到正确的盘片移动顺序. 415  二叉树分析方法 首先 ,将传统的“绕圈子”方式转化为一种层次 清楚明了的树型结构. 表 1   正确的移动次序 移动次数 移动盘片号 移动方向 1 1 a →b 2 2 a →c 3 1 b →c 4 3 a →b 5 1 c →a 6 2 c →b 7 1 a →b 8 4 a →c 9 1 b →c 10 2 b →a 11 1 c →a 12 3 b →c 13 1 a →b 14 2 a →c 15 1 b →c 771 第 3 期             晏建学  王云秋 :递归与树型结构 其次 ,用中序遍历 ,很清楚的知道每次操作移动哪个 盘片 ,从哪根杆移动到哪根杆 ,及每个盘片的移动规 律. 最后 ,只要给出移动的盘片数 n ,就可以知道其 递归调用层次为 n ,递归过程中盘片一共要移动 2n - 1 次 ,第 i 个盘片移动的次数为 2i - 1. 下面 ,我们再来看一看 Ackerman 函数的例子. ①Ackerman 函数的定义 Ack(m ,n) = n + 1          若 m = 0 Ack(m - 1 ,1)       若 n = 0 Ack(m - 1 ,Ack(m ,n - 1)  其它情况 ②PASCAL 程序 FUNCTIONAck (m ,n :integer):integer ;  BEGIN  IF  m = 0  THEN  Ack : = n + 1          ELSE  IF  n = 0             THEN  Ack : = Ack (m - 1 ,1)             ELSE  Ack : = Ack(m - 1 ,Ack(m ,n - 1));  END; ③其对应树型结构(见图 2)   由上图 ,该递归问题第一次调用时 ,即为二叉树 的根结点 ,且该递归问题是函数的多层嵌套. 对应于 树型结构的左结点就是其内嵌函数的逐层深入 ,即 为嵌套关系 ,直到 m = 0 时才能得出结果. 之后 ,又 将值逐层代回到右子树 ,因而右子树是退的关系. 对 该二叉树进行中序遍历也就是该递归的运行过程 , 遍历到最后一个叶子结点的值也就是函数所要求的 值. 一般来说 ,递归问题均可以转化成树型结构 ,进 行分析时具有以下几点优势 : 1. 将传统的“绕圈子”分析方式转化成一种层次 清晰的树型分支结构对递归问题进行分析. 2. 一些复杂或数值较大的递归问题 ,用传统的 “绕圈子”方式无从下手 ,而树型结构可以充分发挥 其易于展开的特性 ,对递归问题清楚再现. 3. 利用树的层次结构和树自身具有的一些性 质 ,更容易把握递归的本质和特性. 应该指出 ,递归按调用方式不同有直接递归和 间接递归 2 种 ,本文所讨论的方法仅只适用于直接 递归分析. (下转 181 页) 871 云南民族学院学报 (自然科学版)               第 11 卷 思索 ,有助于学习的主动性和积极性的提高. 3. 新模式中按传统理科章、节、点的顺序讲解 和穿插其中的实例分析、师生讨论、应用练习、利用 旧知识向新知识的引申介绍等内容 ,对学生逻辑思 维能力发展 ,发散思维和反向思维能力的培养都有 益处 ,有助于学生的自主建构知识能力的提高 ,更有 助于其探究精神和创新精神的培养. 4. 新模式对学生多种能力 ,如教学信息的采集 分析能力 ,教材和参考书的阅读和归纳总结能力 ,语 言表达能力 ,质疑和析疑能力培养以及合作讨论习 惯养成等也有促进作用. 经过近两年的实践 ,我们体会到新的教学模式 不但开阔了学生的知识视野 ,也给教师在专业知识 水平、相关知识的整合、教育理论的学习、信息化素 养和计算机使用能力以及对学生情况的掌握等方面 提出了更高的要求. 形成一种新教学模式需要教师 去积极学习与思考 ,应用好一种教学模式更要求教 师去深入研究和实践. 教师只有把一般的教学模式 与实际的教学情况相结合 ,才能找到适合自己的课 堂教学的好模式 ,搞好课堂教学 ,最终实现提高教学 质量的目的. 参  考  文  献 [1]  何克抗. 建构主义 —革新传统教学的理论基础[J]. 学科教育 , 1998(3):29 - 31 [2]  张建伟 ,陈琦. 从认知主义到建构主义[J]. 北京师范大学学报 (社科版),1996 ,136(4):75 - 82 [3]  刘志广. 仪器分析 MMCAI 1. 0[M]. 北京 :高等教育出版社 ,1999. 32 - 58 Design and Application of the Instruction Mode of Chromatography Analysis on CAICourseware DAIYun (Chemistry Department of Yunnan University for Nationalities ,Kunming , 650031 ,China) Abstract :By the helping of CAI courseware ,suing the theory of the constructivism , designing a instruction mode of the chromatography analysis course ,introducing the applying conditions and the results of the mode. Key words :CAI courseware ,  Constructivism ,  Chromatography analysis ,  Instruction mode (上接 178 页) 参  考  文  献 [1]  严蔚敏 ,吴伟民编著. 数据结构[M]. 北京 :清华大学出版社 ,1992. 182 - 185 [2]  林夏水编著. 分形的哲学漫步[M]. 北京 :北京师范大学出版社 ,2000. 13 - 16. [3]  N. 沃思. 算法 + 数据结构 = 程序[M]. 北京 :科学出版社 ,1980. 210 - 220 On Nest with Tree -Structure YANJian2xue  WANGYun2qiu (Fundamental Department of Yunnan Finance &Trade Institute ,Kunming , 650221 ,China) Abstract :In this paper , author writer discusses on nest with tree - structure based on that tree - structure is a definition using nest itself. Key words :Nest ,  Layer ,  Tree2structure ,  Binary2tree 181 第 3 期             戴  云 :基于 CAI 课件的《色谱分析》教学模式设计及实践
还剩3页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

bnpysse

贡献于2014-02-15

下载需要 3 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf