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