有关递归算法与其转化为非递归算法的探究

开篇：润墨网以专业的文秘视角，为您筛选了一篇有关递归算法与其转化为非递归算法的探究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要递归算法是程序设计中一种重要的工具，基于长时间的实践，发现其存在着一定的优势与缺点。递归法与非递归法存在着一定的区别，同时递归算法不适合某些程序进行计算解决问题，本文重点对其非递归算法转化过程进行分析，以供参考。

【关键词】递归 非递归 算法 条件 实质 转化

1 引言

随着计算机信息技术的不断发展，软件行业与程序设计行业得到了前所未有的发展。越来越多的智能产品离不开先进计算机技术的支持。递归是程序设计中一种重要的解决办法，同时递归法也是一种计算机技术的发展思路，通过递归的方法实现庞大的工作量的简化，以提高工作效率，降低劳动强度，适合社会的高速发展。掌握好递归程序设计算法需要牢固的基础知识，同时经过长期的工作经验总结，才能运用自如。本文通过对递归法与转化而成的非递归算法进行研究，以供参考。

2 递归算法定义

随着程序设计者的意图不同，相互间可能会存在着一定的不协调性。利用递归的算法可以通过对自身程序进行调用，化解成多个小的问题，一一进行解决后对原问题进行解决的过程。对调用过程中的信息进行保存和恢复。递归算法的过程中相对简单，主要分为递推与回归两个部分，递推主要是为了得到问题的角，把问题推向更简单的方向，回归主要是指在简单的问题得到解答后，回归到原来的复杂问题中。在递归算法的实际应用过程中，递归算法所涉及到的参数与局部变量是有层次区分的。

3 递归算法的条件与优缺点

当在程序中需要解决的问题可以向另一个问题进行转化时，二者在解决办法相同，但处理的对象有所不同，这是递归算法应用时的一个基本条件，另外就是具备终止的递归条件，在转化的过程中，在特定条件已经得到解，无需再继续进行分解。递归设计的本质是当一个复杂的问题可以分解成几个子问题来进行处理时，这些子问题与原来的问题分析处理方法相同。当子问题解决时，原来的问题自然也就解决了，递归的定义归纳项就是对这种转化关系进行描述。

例 求n!(n为正整数) 。

一般的方法：

n! = 1*2*…*(n-1)*n

递归的方法：

int factorial(int n)

{int x;

if (n==0)

x=1;

else

x=factorial (n-1)*n;

return(x);

}

在案例中直接调用factorial(n-1)本身函数进行求解的办法进行，称为直接递归函数。

每一种算法都存在客观的优缺性，递归算法的优点是结构非常清晰，可读性强，而且容易使用数学归纳的方法来对算法的正确性进行证明，给调试程序带来了极大的便利，同时递归算法也有其缺点，它的运行效率偏低，在耗费的计算时间、存储空间都相对于非递归算法要多的多。

4 如何进行非递归算法转化

基于递归算法有优点和缺点，在运用时要对方法进行有效的选择，才能有效求解。经过长期的发展，人们更愿意采用递归的算法来对问题进行分析，而对于问题的求解则是多通过非递归算法来进行，这其中就需要将递归算法转化为非递归的算法。

转化过程就是分析的过程，把递归算法转换成非递归算法是对递归函数系统的执行过程的一种模拟，这种构造的非递归算法语句较多，但由于固定方法可以遵循，在实际的软件设计使用的频率较多。首先对栈S进行初始化，给每一个递归的函数入口分别进行不同的标号，每个返回处设立一个标号，把每个递归函数的递归调用进行如下操作转化。对现场进行保留，开辟存储空间，准备数据，转入相应的进归函数执行。 在特殊情况下也可以进行简化，简化规则主要有三种方式。如果在递归算法只有一处递归调用或多个调用返回时，所执行的语句都相同，则在转换时，返回地址可以不必入栈，只为参数设立栈进行保存。

递归算法转化为非递归算法主要有三种形式。首先是通过分析，不用分解，直接用循环的算法实现求解；二是自己运行时栈,对分析过程中的信息进行存储,转化为非递归算法替代递归算法；三是利用栈保存参数,由于栈本身具有典型的先进后出的性质，与递归算法的执行过程相匹配,因而可利用非递归算法来对递归算法进行替代。本文主要对直接转化与借助借助栈实现转化。

4.1 直接转化法

在递归算法的函数中，递归调用语名只有一个，这种递归称为尾递归，这个调用语句位于函数的最末端，当调用返回时，返回到上一层算法的结束处。用迭代形式来对其进行代替，不再使用系统运行时的栈来对信息进行保护。阶乘求解就可以写成如下所示的非递归算法。

LongUnfac(long n){//阶乘非递归算法

Long product=1;

For(int i=1; i

Product=product*i;

Return product; }

4.2 借助栈实现转化

递归在调用时与在调用过程中重要的一环是递归函数运行的层次。层次具有典型的重要意义，调用该函数的主函数如果是第0层开始的话，从主函数调用递归函数在进入到第1层，以此类推，在第i层递归调用函数为进入到下一层（i+1层）。相反，则会退到i-1层。为了确保运行过程能够正常操作，系统需要设置“递归工作栈”，来作为递归函数运行期间使用的数据存储区。每一个层的递归所需要的信息都会形成一个工作记录，相当于痕迹，记录着相关的参数据，工作记录中包括递归所需要的信息，有实在参数、局部变量与上层的返回地址等。当进入到层递归时，将形成新的工作记录，而退出一层时，将会在栈顶弹出一个工作记录。通过栈来实现非递归转化具有典型的意义，目前应用较为广泛

5 结语

递归算法有其自身的优势与缺点，与非递归算法在运行的效率上与适应性方面有所不同。本文通过对递归算法与非递归算法的转化思路分析，不断提高其执行效率，解决目前面临的实际问题。针对不同的运行环境与要求，需要选择不同的算法，不可盲目地用栈来对递归进行消解。采用借助栈的方式进行转化并不能切实提高计算机求解问题的运行时间，但可以节省系统的堆栈，适合于不支持递归机制的语言进行程序设计。随着计算机编程技术的不断进步，将会出现新的算法，提高运行效率，适用于更多的计算环境与要求。

参考文献

[1]马海瑛.数据结构中递归算法的描述与实现[J].大众科技,2007,03:177-178+153.

[2]马军红.递归与非递归算法比较及效率分析[J].科技信息,2008,31:554+566.

[3]高鹭,周李涌.递归算法及其转化为非递归算法的分析[J].科技资讯,2008,30:210.

[4]聂雅卓,周步祥,林楠,高志勇,刘金华.多电压等级电网可靠性递归原理及其递推算法[J].电力系统及其自动化学报,2012,05:117-122.

[5]李伟.浅析C语言递归算法[J].电脑知识与技术,2012,30:7229-7235.

[6]汤亚玲.递归算法设计及其非递归化研究[J].计算机技术与发展,2009,11:85-88+93.

[7]杨春花,姚进,赵培英,姜合.一个递归算法非递归化的算法框架[J].计算机应用与软件,2010,09:81-84.

作者简介

李亚琼（1992-），女，苗族，贵州省凯里市人。现为河南大学国际教育学院 计算机科学与技术专业在校学生。

张燕飞（1992-），男，江苏泰兴市人。现为河南大学国际教育学院在校学生。

作者单位

河南大学国际教育学院河南省开封市475001