递归算法分析

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个

17、盘子的时候怎么移动？,使用递归算法解决汉诺塔问题,问题分析： 可以用递归方法求解n个盘子的汉诺塔问题。 基本思想： 1个盘子的汉诺塔问题可直接移动。 n个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱借助C移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再借助A移到C柱。,递归解决汉诺塔示意,汉诺塔递归算法设计,首先，盘子的个数n是必须的一个输入参数，对n个盘子,我们可从上至下依次编号为1,2,n；其次，输入参数还需有3个柱子的代号,我们令3个柱子的参数名分别为fromPeg，auxPeg和toPeg；最后，汉诺塔问题的求解是一个处理过程，因此算法的输

18、出是n个盘子从柱子fromPeg借助柱子auxPeg移动到柱子toPeg的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息： 将第i 个盘子从X 移动到Y 这样，汉诺塔问题的递归算法可设计如下：,汉诺塔递归算法实现,算法测试,测试主函数如下： #include void main() int n;/汉诺塔盘子数目 printf(n 请输入汉诺塔盘子数目:n); scanf(%d, 按下运行按钮观察程序运行的输出信息,运行程序,2.2.4递归寻找线性表最大元素,问题描述：寻找线性表中最大的数据元素。 解决的基本思想： 将线性表分解为a1a2am和am+1an两个子表，分别求取子表的最大值a

19、i和aj，比较ai和aj，得到其最大值就是整个线性表的最大值。 而子表中求取最大值的方法和原表相同。如此不断分解，直到表中只剩下一个数据元素（就是该子表的最大值），,算法实现,运行程序,2.2.5回溯法,回溯法的基本思想： 对一个包括有很多结点，每个结点有若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。 当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯（即退回）到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的分支； 如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯到这个结点的前一结点继续这样的搜索过程； 这样的搜索过程一直进行到搜索到问题的解或搜索完了全

20、部可搜索分支没有解存在为止。,回溯法典型应用迷宫问题,搜索过程：,如何实现迷宫,问题分析： 迷宫问题中包括很多路口，但是每一个路口上最多有三个分支，所以算法可以设计为这样的一个搜索过程：,把整个搜索过程分解为向左、向右、向前三个方向上的子问题的搜索； 当搜索到某一路口时，发现该路口没有可搜索的方向，就让搜索过程回溯到该路口的前一路口，然后搜索回溯后路口其他尚未被搜索的方向，如果发现该路口也无搜索方向，则回溯至这个路口的前一方向继续这样的过程； 直到找到出口或者搜索完毕全部可连通的路口的可能的搜索方向没有找到出口为止。,迷宫的数据结构设计,数据结构设计：要计算机模仿迷宫问题，首先要将迷宫问题数值

21、化，把每一个路口定义为一个包括left、forward、right三个域的结构体，分别表示向前、向左、向右搜索；如果每一个域的值x非0，则表示可以从当前路口到达路口x，否则表示该方向是一个死路。 Typedef struct/路口结构体定义 int left;int forward;int right;/搜索方向 Intesection,描述迷宫的数据应该包括全部的路口数据集合和迷宫的出口数据。为了分析计算方便，往往还包括路口的个数。因此可定义迷宫的结构体如下：,迷宫的数据结构设计,Typedef struct/路口结构体定义 int mazesize;/路口个数 Intesection *i

22、ntSec;/路口集合 int exit;/出口 Maze;一个数据文件表示,6 0 2 0 3 5 6 0 0 4 0 0 0 0 0 0 7 0 0 7,数据文件第一行表示6个路口； 最后一行表示出口；其他每一行表示该路口三个方向的可达性。,迷宫问题的解决,使用上述数据结构描述迷宫 借助递归算法实现搜索和回溯 具体实现自己探索，两周后参考示范程序,2.2.6递归算法绘制分形图形,我们人类生活的世界是一个极其复杂的世界，例如： 喧闹的都市生活、变幻莫测的股市变化、复杂的生命现象、蜿蜒曲折的海岸线、坑坑洼洼的地面等等，都表现了客观世界特别丰富的现象。 基于传统欧几里得几何学的各门自然科学总是把

23、研究对象想象成一个个规则的形体，而我们生活的世界竟如此不规则和支离破碎，与欧几里得几何图形相比，拥有完全不同层次的复杂性。分形几何则提供了一种描述这种不规则复杂现象中的秩序和结构的新方法,分形几何,什么是分形几何？通俗一点说就是研究无限复杂但具有一定意义下的自相似图形和结构的几何学。 什么是自相似呢？例如一棵苍天大树与它自身上的树枝及树枝上的枝杈，在形状上没什么大的区别，大树与树枝这种关系在几何形状上称之为自相似关系；我们再拿来一片树叶，仔细观察一下叶脉，它们也具备这种性质；动物也不例外，一头牛身体中的一个细胞中的基因记录着这头牛的全部生长信息；这些例子在我们的身边到处可见。 分形几何揭示了世

24、界的本质，分形几何是真正描述大自然的几何学。,分形图形绘制过程,更为丰富的分形图形,主要内容,1、递归的概念 2、递归算法的设计方法 3、递归算法的执行过程 4、递归算法的效率分析 5、递归算法的非递归化处理,3、递归算法执行过程,以阶乘的递归计算为例 long Fact(int n) long f; if(n0) printf(n0,input error); else if(n=0|n=1) f=1; else f=Fact (n-1)*n; return(f); ,执行过程分析,程序运行例证,运行程序,递归算法执行过程总结,递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过

25、程； 到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回； 返回到最外层的调用语句时递归算法执行过程结束。,主要内容,1、递归的概念 2、递归算法的设计方法 3、递归算法的执行过程 4、递归算法的效率分析 5、递归算法的非递归化处理,4、递归算法的效率分析,斐波那契数列Fib(n)的递归定义是：,求第n项斐波那契数列的递归函数如下：,long Fib(int n) if(n = 0 | n = 1) return n; /递归出口 else return Fib(n-1) + Fib(n-2); /递归调用 ,斐波那契数列计算的调用过程,用归纳法可以证明求Fib(n)的递归调用次数

26、等于2n-1；计算斐波那契数列的递归函数Fib(n)的时间复杂度为O(2n)。计算斐波那契数列Fib(n)问题，我们也可根据公式写出循环方式求解的函数如下：,Fib(5)的递归调用树,斐波那契数列的循环解决方案,原因分析,上述循环方式的计算斐波那契数列的函数Fib2(n)的时间复杂度为O(n)。对比循环结构的Fib2(n)和递归结构的Fib(n)可发现： 循环结构的Fib2(n)算法在计算第n项的斐波那契数列时保存了当前已经计算得到的第n-1项和第n-2项的斐波那契数列，因此其时间复杂度为O(n)； 而递归结构的Fib(n)算法在计算第n项的斐波那契数列时，必须首先计算第n-1项和第n-2项的

27、斐波那契数列，而某次递归计算得出的斐波那契数列，如Fib(n-1)、Fib(n-2)等无法保存，下一次要用到时还需要重新递归计算，因此其时间复杂度为O(2n) 。,效率分析总结,优点：-递归过程结构清晰 -程序易读 -正确性容易证明 缺点：-时间效率低 -空间开销大，问题规模扩大时，噩 梦来临。 -算法不容易优化 对于频繁使用的算法，或不具备递归功能的程序设计语言，需要把递归算法转换为非递归算法。,主要内容,1、递归的概念 2、递归算法的设计方法 3、递归算法的执行过程 4、递归算法的效率分析 5、递归算法的非递归化处理,5、递归算法的非递归化处理,采用迭代算法 尾递归的消除 利用栈消除任何递

28、归,如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。比较常用的递归形式,5.1迭代法消除递归,采用迭代算法,long Fact2(int n) 用迭代算法求n! x=1; for(i=1;i=n;i+) x*=i; return x; Fact2,5.2尾递归算法及其递归的消除,void Output1(LinkedList L) 顺序输出单链表结点数据的递归算法 if(L) printf(L-data); 输出结点的值 Output1(L=L-next); 尾递归调用 Output1,尾递归的消除-1,使用跳转语句 void Output2(LinkedList L) 顺序输