数据结构中递归算法研究与实现.docVIP

数据结构中递归算法的研究与实现 第 期 总第 期 机 械 管 理 开 发 年 月 6 ( 99 ) 2007 12 No.6 (SUM No.99 ) MECHANICAL MANAGEMENT AND DEVELOPMENT Dec.2007 数据结构中递归算法的研究与实现 郭韶升 张 炜 (青 岛科技大学信息科学技术学 院 山东 青 岛 266042) 【摘 要 】 递归是一种重要 的编程工具, 在数据 结构 中多处使用 。递 归算法掌握 的好坏直接 影 响数据 结构 的学 习, 从数据结构 的角度 出发, 提 出了一种有效 的递归教学方法 。 【关键词 】 递归算法 ;数据结构 ;教学方法 【中图分类号 】 【文献标识码 】 【文章编号 】 ( ) G462 A 1003- 773X 2007 06- 0090- 02 0 引 言 个非递归函数, 反映了递归 问题 的结构 。 递归是软件设计 的重要方法和技术 。递归省略了 (2) 递归原理 。递归是把一个不能或不好直接求 程序设计 中许 多细节操作, 简化 了程序设计过程, 递 解 的 “大 问题 ”转化为一个或几个 “小 问题 ”来解决 ; 再 归 函数结构清 晰 、程序 易读 , 而且它 的正确性容 易得 把这些 “小 问题 ”进 一步转化 为更 小 的 “小 问题 ”来解 到验证 。在许 多实际问题求解 时, 采用递归方法要 比 决 ;如此 “回推 ”, 直到每个 “小 问题 ”都可直接解决 (此 非递归方法容易实现 。 时 “回推 ”到递归出口) ;再从递归出口返 回到原 问题 的 1 递归是程序设计 中强有力 的一个工具 求解过程 [2] 。 (1) 有很多数学函数是递归定义 的, 例如大家熟 求 f (Sn ) 的 “回推 ”过程为 : f (Sn ) →f (Sn - 1 ) → … 悉 的阶乘 函数 Fact (n) = ! 1 若 n = 0 。 →f (S1 ) →f (S0 ) 。一旦遇到递归出 口, “回推 ”过程结 · ( ) 若 n Fact n- 1 n 0 束, 开始求值过程 。所 以 “回推 ”过程是 “量变 ”过程, 即 (2) 有 的数据 结构, 例如二叉树 、广义表, 由于结构本 原来 的 “大 问题 ”在慢慢变小, 但 尚未解决, 遇到递归出 身固有 的递归特性, 它 的许多操作可按递归描述 。(3) 口后, 便发生 了 “质变 ”, 即递归 问题变成 了直接 问题 。 还有一类 问题, 虽然 问题本身没有 明显 的递归性, 但 上面 的求解过程如下 : f (S ) =M →f (S ) =g (f (S ) ,