递归算法分析课件

《递归算法分析课件》由会员分享，可在线阅读，更多相关《递归算法分析课件（73页珍藏版）》请在金锄头文库上搜索。

1、递归算法设计与实现,主要内容,1、递归的概念 2、递归算法的设计方法 3、递归算法的执行过程 4、递归算法的效率分析 5、递归算法的非递归化处理,递归概念的引入,一个小故事： 山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是： 小故事的特点？,由经典故事到程序设计,就象上面的故事那样，故事中包含了故事本身自己调用自己。 程序设计中函数的出现因为对自身进行调用，所以需对程序段进行包装，也就出现了函数。 函数的利用是对数学上函数定义的推广，函数的正确运用有利于简化程序，也能使某些问题得到迅速实现。对于代码中功能性较强的、重复执行的或

2、经常要用到的部分，将其功能加以集成，通过一个名称和相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行简单调用就能来完成特定功能。 例如我们把上面的讲故事的过程包装成一个函数，就会得到：,经典故事的程序设计,函数的功能？ 输出这个故事的内容，等用户按任意键后，重复的输出这段内容。我们发现由于每个故事都是相同的，所以出现导致死循环的迂回逻辑，故事将不停的讲下去。 出现死循环的程序是一个不健全的程序，我们希望程序在满足某种条件以后能够停下来，正如我们听了几遍相同的故事后会大叫：“够了！”。 于是我们可以得到下面的程序：,运行程序,改良的程序,运行程序,1、递归的概念,递归的定义 什么时候使

3、用递归 递归的分类 递归模型的概念,1、递归的概念,递归算法和课程前面讲的内容不同，递归算法不是一种数据结构，而是一种有效的算法设计方法。递归算法是解决很多复杂问题的有效方法！ 在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。,2、什么时候使用递归？,1. 问题的定义是递归的 有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的

4、递归算法。 例如：阶乘函数的定义 1 当n=0时 n！= n*(n-1)*1 当n0时,什么时候使用递归,1 当n=0时 n！= n*(n-1) ！ 当n0时,这时候递归的定义可以用如下的函数表示：,1 当n=0时 f(n)= n*f(n-1) 当n0时,也就是说，函数f(n)的定义用到了自己本身f(n1),第一种递归,阶乘的另外一种定义方法,什么时候使用递归,有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下： typedef struct LNode ElemType data; struct LNode *next; LinkList; 该定义中,

5、结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。,2. 数据结构是递归的,第二种递归,什么时候使用递归,对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下： int Sum(LinkList *head) if (head=NULL) return 0; else return(head-data+Sum(head-next); ,什么时候使用递归,一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法,有序数组元素为1；3；4;5

6、;17;18;31;33; 寻找值为17的数据,3. 问题的求解方法是递归的,第三种递归,什么时候使用递归,折半查找无非就是三种情况，其中两种情况的问题解法如果以算法来表示，都存在算法调用自身的情况。,递归算法的特点就是：将问题分解成为形式上更加简单的子问题来进行求解。递归算法不但是一种有效的分析问题方法，也是一种有效的算法设计方法，是解决很多复杂问题的重要方法。,折半查找中的递归现象总结,典型的三种情况使用递归,1、问题的定义是递归的 2、数据结构是递归的 3、问题求解的过程是递归的,递归的分类,直接递归：函数直接调用本身。 A( ) CALL A( ) . 间接递归：一函数在调用其他函数时

7、，又产生了对自身的调用。 A( ) B( ) CALL B（） CALL A（） ,递归模型,递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 其中,第一个式子给出了递归的终止条件,第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系,我们把第一个式子称为递归出口,把第二个式子称为递归体。,一般地,一个递归模型是由递归出口和递归体两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。 实际上递归的思路是把一个不能或者不好直接求解的“大问题”转化为一

8、个或者几个“小问题”来解决； 再把“小问题”进一步分解为更小的“小问题”来解决；如此分解，直到“小问题”可以直接求解。,递归出口,递归模型的分解过程不是随意分解，分解问题规模要保证“大问题”和“小问题”的相似性，即求解过程和环境要具备相似性； 一旦遇到递归出口，分解过程结束，开始求值，分解是量变的过程，大问题慢慢变小，但是尚未解决，遇到递归出口之后，发生了质变，即递归问题转化为直接问题。 因此，递归算法的执行总是分为分解和求值两个部分。,递归模型的抽象表达,递归出口的一般格式如下 f(s1)=m1 递归体的一般格式 f(sn)=g(f(sn-1),c) 递归的分解过程 递归求值的过程,主要内容

9、,1、递归的概念 2、递归算法的设计方法 3、递归算法的执行过程 4、递归算法的效率分析 5、递归算法的非递归化处理,2、递归算法的设计,递归的求解的过程均有这样的特征： 先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,分别求解,如此反复进行,直到不能再划分成子问题,或已经可以求解为止。 这种自上而下将问题分解、求解,再自上而下引用、合并,求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。,2.1递归算法设计步骤,(1)对原问题f(s)进行分析,假设出合理的“较小问题”f(s

10、)(与数学归纳法中假设n=k-1时等式成立相似)； (2)假设f(s)是可解的,在此基础上确定f(s)的解,即给出f(s)与f(s)之间的关系(与数学归纳法中求证n=k时等式成立的过程相似)； (3)确定一个特定情况(如f(1)或f(0)的解,由此作为递归出口(与数学归纳法中求证n=1时等式成立相似)。,递归算法与数学归纳法,数学归纳法表明，如果我们知道某个论点对最小的情形成立，并且可以证明一个情形暗示着另一个情形，那么我们就知道该论点对所有情形都成立。 从数学归纳法的角度来看，递归的分解式相当于数学归纳法归纳步骤的内容，但是仅凭归纳无法完成证明，还必须事实的确定，即最小情况下事情显然可以解决

11、的。 综上所述，数学归纳法是一种证明方法，递归是一种程序设计与实现的方法，数学归纳法是递归算法设计的基础。,2.2设计案例,2.2.1、阶乘函数 2.2.2、斐波那契数列 2.2.3、汉诺塔问题 2.2.4、线性表最大（小）元素问题 2.2.5、回溯法 2.2.6、分形算法,2.2.1阶乘函数n！,分析 n!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。 步骤1 描述递归关系 。 递归关系是这样的一种关系。设U1,U2,U3,Un是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。 注意到，当n=1时，n!=n*(n-1

12、)!（n=0时，0!=1），这就是一种递归关系。对于特定的k!，它只与k与(k-1)!有关。 步骤2 确定递归边界。 在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。,使用递归算法计算阶乘,使用递归算法计算阶乘,运行程序,2.2.2斐波那契数列,在700多年前，意大利有一位著名数学家斐波那契在他的算盘全集一书中提出了这样一道有趣的兔子繁殖问题。 如果有一对小兔，每一个月都生下一对小兔，而所生下的每一对小兔在出生后的第三个月也都生下一对小兔。那么，由一对兔子

13、开始，满一年时一共可以繁殖成多少对兔子？用列举的方法可以很快找出本题的答案： 第一个月，这对兔子生了一对小兔，于是这个月共有2对（1+1=2）兔子。 第二个月，第一对兔子又生了一对兔子。因此共有3对（1+2=3）兔子。 第三个月，第一对兔子又生了一对小兔而在第一个月出生的小兔也生下了一对小兔。所以，这个月共有5对（2+3=5）兔子。 第四个月，第一对兔子以及第一、二两个月生下的兔子也都各生下了一对小兔。因此，这个月连原先的5对兔子共有8对（3+5=8）兔子。 列表如下：,就是说，由一对兔子开始，满一年时一共可繁殖成377对小兔。,斐波那契数列的规律,特别值得指出的是，数学家斐波那契没有满足于这

14、个问题有了答案。他进一步对各个月的兔子对数进行了仔细观察，从中发现了一个十分有趣的规律，就是后面一个月份的兔子总对数，恰好等于前面两个月份兔子总对数的和，如果再把原来兔子的对数重复写一次，于是就得到了下面这样的一串数：1，1，2，3，5，8，13，21，34，55，89，144，233，377后来人们为了纪念这位数学家，就把上面这样的一串数称作斐波那契数列，把这个数列中的每一项数称作斐波那契数。斐波那契数具有许多重要的数学知识，用途广泛。,递归计算斐波那契序列,斐波那契数列Fib(n)的递归定义是：,求第n项斐波那契数列的递归函数如下：,long Fib(int n) if(n = 0 | n

15、 = 1) return n; /递归出口 else return Fib(n-1) + Fib(n-2); /递归调用 ,斐波那契递归调用过程,运行程序,2.2.3汉诺塔问题,汉诺塔(Hanoi tower)问题 传说在古代印度的贝拿勒斯神庙，有一块黄铜板上插了3根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着64个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面3条规则：第一，一次只能移动一个金盘。第二，每个金盘只能由一根宝石柱移到另外一根宝石柱。第三，任何时候都不能把大的金盘放在小的金盘上。神话说，如果僧人把64个金盘完全地从一根宝石柱移到了另外一

16、根上，传说中的末日就要到了世界将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。,世界末日真的会来吗？,移动金盘是个很繁琐的过程。通过计算，对于64个金盘至少需要移动2的64次方，等于1.8乘以10的19次方。 如果僧侣移动金盘一次需要1秒钟，移动这么多次共需约5845亿年。把这个寓言和现代科学推测对比一下倒是有意思的。按照现代的宇宙进化论，恒星、太阳、行星（包括地球）是在三十亿年前由不定形物质形成的。我们还知道，给恒星特别是给太阳提供能量的“原子燃料”还能维持100150亿年。因此，我们太阳系的整个寿命无疑要短于二百亿年。可见远不等僧侣们完成任务，地球早已毁灭了。,我们来试验一下汉诺塔,6个盘子的时候怎么移动？,使用递归算法