形式推导支持的递归程序向非递归程序的转换  

A Framework for Algorithms' Formal Derivation with Recursive Structures

作　　者：化志章[1] 揭安全[1] 李云清[1] 薛锦云[1] 

机构地区：[1]江西师范大学计算机信息工程学院

出　　处：《计算机工程与科学》2007年第10期145-147,F0003,共4页Computer Engineering & Science

基　　金：国家973计划资助项目(2003CCA02800);国家自然科学基金资助项目(60273092);江西省教育厅科技项目(2005-90)

摘　　要：本文提出一种递归消除的方法,适于一类基于递归数据结构的程序。该方法将递归程序作为初始规约,以求解过程的状态变迁序列作迭代模式;通过数据展开和变换实现初始规约向基于序列描述规约的变换,继而用PAR形式推导出序列规约的递推关系,并以之为核心近乎机械地构造出非递归算法。树和图的两个算法实例说明了本方法的有效性。An approach to recursion removing is prompted, which suits for the reeursive programs with reeursive aata structures. It takes the reeursive program as an initial specification, and the state transformation sequence of the solving process as an iterative model By data transformation, the transformation from the initial specification to the sequence-based description specification is implemented,and thus the sequence speeifieation＇s reeursive relationship is derived using the PAR method. The non-reeursive program is constructed almost automatically from recurrence. Two algorithms of trees and graphs are derived to illustrate the validity.

关 键 词：算法推导 形式方法 递归程序变换 PAR方法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]