资源描述：
《专题讲座--递归算法设计ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、递归算法设计与实现电信学院电子信息系杨帆主要内容1、递归的概念2、递归算法的设计方法3、递归算法的执行过程4、递归算法的效率分析5、递归算法的非递归化处理递归概念的引入一个小故事：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：……小故事的特点？由经典故事到程序设计就象上面的故事那样，故事中包含了故事本身——自己调用自己。程序设计中函数的出现——因为对自身进行调用，所以需对程序段进行包装，也就出现了函数。函数的利用是对数学上函数定义的推广，函数的正确运用有利于简化程序，也能使某些问题得到迅速实现。对于代码中功能性较强的、重复执
2、行的或经常要用到的部分，将其功能加以集成，通过一个名称和相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行简单调用就能来完成特定功能。例如我们把上面的讲故事的过程包装成一个函数，就会得到：经典故事的程序设计函数的功能？——输出这个故事的内容，等用户按任意键后，重复的输出这段内容。我们发现由于每个故事都是相同的，所以出现导致死循环的迂回逻辑，故事将不停的讲下去。出现死循环的程序是一个不健全的程序，我们希望程序在满足某种条件以后能够停下来，正如我们听了几遍相同的故事后会大叫：“够了！”。于是我们可以得到下面的程序：运行程序改良的程序运行程序1、递归的概念递归的定义什么时候使用递归递归的分
3、类递归模型的概念1、递归的概念递归算法和课程前面讲的内容不同，递归算法不是一种数据结构，而是一种有效的算法设计方法。递归算法是解决很多复杂问题的有效方法！在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。2、什么时候使用递归？1.问题的定义是递归的有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。例如：阶乘函数的定义1当
4、n=0时n！=n*(n-1)*…*1当n>0时什么时候使用递归1当n=0时n！=n*(n-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是一种指向自身类型的指针,所以它
5、是一种递归数据结构。2.数据结构是递归的第二种递归什么时候使用递归对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表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的数据3.问题的求解方法是递归的第三种递归什么时候使用递归折半查找无非就
6、是三种情况，其中两种情况的问题解法如果以算法来表示，都存在算法调用自身的情况。递归算法的特点就是：将问题分解成为形式上更加简单的子问题来进行求解。递归算法不但是一种有效的分析问题方法，也是一种有效的算法设计方法，是解决很多复杂问题的重要方法。折半查找中的递归现象总结典型的三种情况使用递归1、问题的定义是递归的2、数据结构是递归的3、问题求解的过程是递归的递归的分类直接递归：函数直接调用本身。A(){……CALLA()......}间接递归：一函数在调用其他函数时，又产生了对自身的调用。A()B(){……{……CALLB（）CALLA（）……}……}递归模型递归模型是递归算法的抽象,它反映一个递
7、归问题的递归结构,例如,前面的递归算法对应的递归模型如下：fun(1)=1(1)fun(n)=n*fun(n-1)n>1(2)其中,第一个式子给出了递归的终止条件,第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系,我们把第一个式子称为递归出口,把第二个式子称为递归体。一般地,一个递归模型是由递归出口和递归体两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。实际上递归
