基于状态机的递归算法非递归化框架  

NON-RECURSIVE CONVERSION FRAMEWORK OF RECURSIVE ALGORITHM BASED ON STATE MACHINE

作　　者：杨硕 周霜菊[2] 张志杰[3] Yang Shuo;Zhou Shuangju;Zhang Zhijie(College of Computer Science and Technology,Shenyang University of Chemical Technology,Shenyang 110142,Liaoning,China;Academy of Arts and Films,Chengdu University,Chengdu 610106,Sichuan,China;School of Computer Science and Technology,Southwest Minzu University,Chengdu 610041,Sichuan,China)

机构地区：[1]沈阳化工大学计算机科学与技术学院,辽宁沈阳110142 [2]成都大学美术与影视学院,四川成都610106 [3]西南民族大学计算机科学与技术学院,四川成都610041

出　　处：《计算机应用与软件》2018年第4期122-128,共7页Computer Applications and Software

基　　金：成都大学龙泉驿区汽车创意设计试点区项目(2015-CX00-00010-ZF);辽宁省教育厅基金项目(L2014171);四川省科技支撑计划项目(2016GZ0396)

摘　　要：由递归程序转换到非递归程序可以避免栈内存溢出问题并可以提高算法效率。借助状态机编程的思想,提出一种递归到非递归转换的框架。将函数的调用和返回过程看作是状态的转换,并将递归过程模拟为"进入函数"、"进入递归点"、"从递归点返回"等状态。实验中,将几种具有代表性的递归算法转换为非递归算法,从转换后代码可以看出,提出的框架与"while-while"和"while-if"等常见框架相比,具有结构清晰、代码简洁和转换过程程序化强的优点。Converting recursive algorithms to non-recursive ones can avoid the error of stack overflow and improve algorithm running efficiency.Thus,a conversion framework,which is benefit from state machine,is proposed.In this framework,the actions of function calling and returning are considered as state transition,and the recursive procedures are encoded by″entering function″,″entering recursive point″and″returning from recursive point″et al.In experiments,the conversions of several classic recursive algorithms show that,compared with the framework of″while-while″or″while-if″et al.,the proposed framework has the advantages of clear structure,compact codes,and more programmatic conversion procedure.

关 键 词：状态机 栈 递归算法 非递归算法 框架 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]