[精品]算法分析论文

《[精品]算法分析论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》论文题目指导老师吴晟学生姓名林金香学生学号200916021204学院专业班级计科091关于递归算法的认识摘要：本文介绍了我对递归算法的认识，主要分为递归算法的特点，递归过程的描述，递归算法的适用范围，优缺点及基于C++实现的编程实例几个部分。递归算法就是把问题转化为规模缩小的同类问题的子问题，然后递归调用函数或过程來求出问题的解。这种算法是一种直接或间接地调用自身的算法。用函数自身给岀定义的函数称为递归函数。递归算法充分地利用了计算机系统内部功能，自动实现调用过程屮对相关H必要的信息的保存与恢复，从而省略了求解过程许多细节的描述。在计算机编写程序中，递归算法对解决一大

2、类问题是十分冇效的，它往往使算法得描述简洁而H易于理解，故递归算法是训练有素的软件设计人员设计算法的常用方法。关键字：递归算法子问题自身调用在上学期数据结构的学习中，我们已经初步了解了递归算法的定义，而本学期的算法设计与分析让我进一步认识了递归算法的木质，递归算法是存在自身调用的算法，在编程实现中，即使是较为复杂的问题，通过递归來实现也能拥冇非常简洁而直观的代码形式，从而使我们的编码大大简化，但没有一种算法是完美的，递归算法同样存在局限性，并不是所有的语言都支持递归，递归在内存的消耗上也造成巨大的浪费。下面我把自己对递归算法的认识总结如下。递归算法的特点：递归就是在函数或子过程的内部，肓

3、接或间接地调用自己的算法；递归算法是从下往上进行思维，需要对问题有全局的了解；在使用递归算法时，必须至少测试一个可以终止递归的条件，并且还必须对在合理的递归调用次数内未满足此类条件的情况进行处理，如果没有一个在正常情况下可以满足的条件，则过程将陷入执行无限循环的高度危险之屮；递归算法的描述非常简洁而易于理解，但因重复计算和较人的堆栈消耗使递归算法的解题的运行效率较低；并不是所有的语言都支持递归，在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢击等不利编程的因素,所以一般不提倡用递归算法设计程序。递归过程：递归过程是直接调用自己或通过一系列的过程调

4、用语句间接调用自己的过程。在一个过程的运行期间调用另一个过程吋，在执行被调用过程之前,系统要先把所冇的实在参数返回地址等信息传递给被调用的过程保存，为被调用过程的局部变量分配存储空间，将控制转移到被调用入口。接下来从被调过程返冋调用过程要保存被调用过程的计算结果，释放被调用过程的数据区，依照被调过程保存的返冋地址将控制转移到调用过程。该过程服从后调用先返冋的原则。递归算法的适用范围：由于递归算法的运行效率较低，堆栈容易溢出的特点,递归算法适用于问题规模较小且那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题，这样可以减少代码的复朵度。递归算法所适用的问题一般有

5、这样的特征：为求解规模为N的问题，设法先将它分解为规模较小的子问题，然后从这些子问题的解构造出整个问题的解，并且这些子问题也能采用同样的分解和综合方法，分解成规模更小的子问题，并从这些更小的子问题的解构造出较大规模的问题的解，特别地，当规模N=1时，能直接得解。例如很多的数学函数是递归定义的（阶乘函数）、有的数据结构（广义表，二叉树）述冇一类本身没冇明显的递归结构但用递归求解更为简单的问题（汉诺塔问题，八皐后问题）。递归算法的优缺点：递归算法易于理解，结构清晰，所编写的代码简洁精练,可读性好，有利丁代码的维护。然而递归算法的效率却较低，占用较大的内存开销，消耗更多的系统堆栈，算法的空间复

6、杂度大，故可以实现的深度是有限制的。而且要考虑函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法。递归与递推的关系：1、递推法是求解递归方程的基本方法，对于某些递归关系可由逐级递推求得递归方程的解。2、递归算法会引起一系列的函数调用，并且可能会有一系列的重复计算，所以当某个递归算法能较方便地转化成递推算法时，通常按递推算法编写程序。递归算法的执行过程分递推与冋归两个阶段。在递推阶段，把较复杂的问题（规模为N）的求解推到比原问题简单一些的问题（规模小于N）的求解。在回归阶段，当获得最简单的情况后，逐级返回，依次获得稍复杂问题的解

7、。递推是利用问题本身所具有的递推关系对问题求解的一种方法。采用递推法建立起来的算法一般要有重要的递推性质，即当求得问题规模为11的解后，由问题的递推性质，能从已求得的规模为1,2,i-1的一系列的解，构造出问题规模为i的解。若设这种问题的规模为N,当N=0或”二1时・，解或为已知，或能很容易地求得。编程实例：递归算法采用自身调用的思想使我们的程序代码大大的简化，然而递归的思维和我们的常规思维却是相逆的，我们正常的思维逻辑是从上向下考