数据结构与算法分析论文(递归的讨论).docVIP

数据结构论文——递归算法的讨论 所谓递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内，直接或者间接地调用自己的算法。递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点： (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 (3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。在函数中调用函数自身，不断调用，直到满足函数得出计算结果(某个条件)因为其需要不断循环的调用自身，所以称为递归调用。递归的原理,其实就是一个栈(stack),?比如求5的阶乘,要知道5的阶乘,就要知道4的阶乘,4又要是到3的,以此类推,所以递归式就先把5的阶乘表示入栈,?在把4的入栈,直到最后一个,之后呢在从1开始出栈,?看起来很麻烦,确实很麻烦,他的好处就是写起代码来,十分的快,而且代码简洁,其他就没什么好处了,运行效率出奇的慢从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事递归分为2种，直接递归和间接递归。直接递归，比如方法A内部调用方法A自身间接递归，比如方法A内部调用方法B，方法B内部调用方法C，方法C内部调用方法A 1 当n=0时 n！= n*(n-1)*…*1 当n0时 这时候递归的定义可以用如下的函数表示： 1 当n=0时 f(n)= n*f(n-1) 当n0时 也就是说，函数f(n)的定义用到了自己本身f(n－1)。 ②数据结构是递归的。 有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LinkList; 该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。 对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下： int Sum(LinkList *head) { if (head==NULL) return 0; else return(head-data+Sum(head-next)); } ③问题求解的过程是递归的。 一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法。有序数组元素为1；3；4;5;17;18;31;33;寻找值为17的数据（如上图）。 折半查找无非就是三种情况，其中两种情况的问题解法如果以算法来表示，都存在算法调用自身的情况。 递归算法的特点就是：将问题分解成为形式上更加简单的子问题来进行求解。递归算法不但是一种有效的分析问题方法，也是一种有效的算法设计方法，是解决很多复杂问题的重要方法。 递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。 利用递归算法解题，首先要对问题的以下三个方面进行分析： 1、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。 2、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。 3、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。