算法与结构课件第二章递归(华北电力大学科技学院).ppt

计算机算法设计与分析,North China Electric Power University,Computer Algorithms Design&Analysis,华北电力大学计算机科学与工程系,Dept.of Computer Science&Engineering of North China Electric Power University,第二章 递归(Recursion),递归的概念,递归算法的应用和实现,递归问题的非递归算法,North China Electric Power University,递归方程渐进阶的求法,生成函数,1 递归的概念,North China Electric Power University,一个直接或间接调用自身的算法称为递归算法。一个使用函数自身给出定义的函数称为递归函数。,例 阶乘函数 阶乘函数的定义为：,n!=,1 n=0,n(n-1)!n0,定义式的左右两边都引用了阶乘记号，是一个递归定义式，可递归地定义如下：,int Factorial(int n)if(n=0)return 1;return n*Factorial(n-1);,2 递归算法的应用和实现,如果问题的数据结构是递归的，问题的定义是递归的，问题的解法是递归的，可以考虑用递归算法。,看下面的数据结构：,Head,Head,这是单链表，每个结点有两个域：数据域和指针域。它是一种递归的结构，可定义为：1)一个结点，其指针域为null，是一个单链表；2)一个结点，其指针域为有效指针指向一个单链表，仍是一个 单链表。,1)问题的数据结构是递归的,North China Electric Power University,若存在如上定义的一个单链表，现要实现打印最后一个结点的数据域的值，可用下面递归过程：,template class link_list Type data;link_list*next;template void search1(link_list*h)if(h-next=null)coutdata;else search1(h-next);,North China Electric Power University,North China Electric Power University,二叉树(Binary Tree)也是一种递归的数据结构，其递归定义为：1)它是一棵空树；2)它是由一个根结点和两棵分别称为左右子树的二叉树构成。,要遍历一棵二叉树可以采用下面的递归算法：,void Traverse(Bitptr*t)if(t!=null)coutdata;Traverse(t-lchild);Traverse(t-rchild);,North China Electric Power University,例：Fibonacci数列 无穷数列1,1,2,3,5,8,13,21,34,55,称为Fibonacci数列。它可以递归地定义为：,Fib(n)=,1 n=0,1 n=1,Fib(n-1)+Fib(n-2)n1,第n个Fibonacci数可递归地计算如下：int Fibonacci(int n)if(n=1)return 1;return Fibonacci(n-1)+Fibonacci(n-2);,上述两例中的函数也可用如下非递归方式定义：,n!=1*2*3*(n-1),2)问题的定义是递归的,North China Electric Power University,例：整数划分问题,将一个正整数n表示成一系列正整数之和，n=n1+n2+nk，其中n1n2nk 1,k 1正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同划分个数称为正整数n的划分数，记做p(n)。,如正整数6有如下11种不同的划分，所以p(6)=11。6;5+1;4+2,4+1+1;3+3,3+2+1,3+1+1+1;2+2+2,2+2+1+1,2+1+1+1+1,1+1+1+1+1+1;,3)问题的解法是递归的,North China Electric Power University,在正整数n的所有不同的划分中，将最大加数n1不大于m的划分个数记作q(n,m)。我们可以建立如下递归关系：1)q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式。2)q(n,m)=q(n,n)，mn;最大加数n1实际上不能大于n，因此,q(n,m)=q(n,n)。3)q(n,n)=1+q(n,n-1)；正整数n的划分由n1=n和n1n-1的划分组成。4)q(n,m)=q(n,m-1)+q(n-m,m)，nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1 m-1的划分组成。以上的关系实际上给出了计算q(n,m)的递归式如下：,q(n,m)=,1 m=1,q(n,n)nm,1+q(n,n-1)n=m,q(n,m-1)+q(n-m,m)nm1,0 n1或m1,递归算法的设计方法,递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求解问题的基本思想是：对于一个较为复杂的问题，把原问题分解成若干个相对简单且类同的子问题,这样，原问题就可递推得到解。适宜于用递归算法求解的问题的充分必要条件是：（1）问题具有某种可借用的类同自身的子问题描述的性质；（2）某一有限步的子问题（也称作本原问题）有直接的解存在。当一个问题存在上述两个基本要素时，该问题的递归算法的设计方法是：（1）把对原问题的求解设计成包含有对子问题求解的形式。（2）设计递归出口。,例 设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的描述是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。,问题分析：可以用递归方法求解n个盘子的汉诺塔问题。,基本思想：1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再移到C柱。4个盘子汉诺塔问题的递归求解示意图如图6-4所示。,图6-4 汉诺塔问题的递归求解示意图,Y,X,Z,以三个盘为例：,A,B,C,算法设计：首先，盘子的个数n是必须的一个输入参数，对n个盘子,我们可从上至下依次编号为1,2,n；其次，输入参数还需有3个柱子的代号,我们令3个柱子的参数名分别为fromPeg，auxPeg和toPeg；最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是n个盘子从柱子fromPeg借助柱子auxPeg移动到柱子toPeg的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：Move Disk i from Peg X to Peg Y这样，汉诺塔问题的递归算法可设计如下：,void towers(int n,char fromPeg,char toPeg,char auxPeg)if(n=1)/递归出口printf(%s%c%s%cn,move disk 1 from peg,fromPeg,to peg,toPeg);return;/把n-1个圆盘从fromPeg借助toPeg移至auxPegtowers(n-1,fromPeg,auxPeg,toPeg);/把圆盘n由fromPeg直接移至toPegprintf(%s%d%s%c%s%cn,move disk,n,from peg,fromPeg,to peg,toPeg);/把n-1个圆盘从auxPeg借助fromPeg移至toPegtowers(n-1,auxPeg,toPeg,fromPeg);,测试主函数如下：#include void main(void)Towers(4,A,C,B);程序运行的输出信息如下：,Move Disk 1 from Peg A to Peg BMove Disk 2 from Peg A to Peg CMove Disk 1 from Peg B to Peg CMove Disk 3 from Peg A to Peg BMove Disk 1 from Peg C to Peg AMove Disk 2 from Peg C to Peg BMove Disk 1 from Peg A to Peg BMove Disk 4 from Peg A to Peg CMove Disk 1 from Peg B to Peg CMove Disk 2 from Peg B to Peg AMove Disk 1 from Peg C to Peg AMove Disk 3 from Peg B to Peg CMove Disk 1 from Peg A to Peg BMove Disk 2 from Peg A to Peg CMove Disk 1 from Peg B to Peg C,总结如下：递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束。,代码,递归过程的实现,对于非递归函数，调用函数在调用被调用函数前，系统要保存以下两类信息：（1）调用函数的返回地址；（2）调用函数的局部变量值。当执行完被调用函数，返回调用函数前，系统首先要恢复调用函数的局部变量值，然后返回调用函数的返回地址。递归函数被调用时，系统要作的工作和非递归函数被调用时系统要作的工作在形式上类同，但保存信息的方法不同。,递归函数被调用时，系统的运行时栈也要保存上述两类信息。每一层递归调用所需保存的信息构成运行时栈的一个工作记录，在每进入下一层递归调用时，系统就建立一个新的工作记录，并把这个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调用，就退栈一个工作记录。因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录，所以栈顶的工作记录也称为活动记录。,设计举例,一般递归算法设计举例,例1 设计一个输出如下形式数值的递归算法。n n n.n.3 3 3 2 21,问题分析：该问题可以看成由两部分组成：一部分是输出一行值为n的数值；另一部分是原问题的子问题，其参数为n-1。当参数减到0时不再输出任何数据值，因此递归的出口是当参数n0时空语句返回。算法设计：递归算法设计如下：void Display(int n)int i;for(i=1;i 0)Display(n-1);/递归/n=0为递归出口，递归出口为空语句,代码,例6-6 设计求解委员会问题的算法。委员会问题是：从一个有n个人的团体中抽出k(kn)个人组成一个委员会，计算共有多少种构成方法。问题分析：从n个人中抽出k(kn)个人的问题是一个组合问题。把n个人固定位置后，从n个人中抽出k个人的问题可分解为两部分之和：第一部分是第一个人包括在k个人中，第二部分是第一个人不包括在k个人中。对于第一部分，则问题简化为从n-1个人中抽出k-1个人的问题；对于第二部分，则问题简化为从n-1个人中抽出k个人的问题。图6-7给出了n=5,k=2时问题的分解示意图。,图6-7 委员会问题分解示意图,当n=k或k=0时，该问题可直接求解，数值均为1，这是算法的递归出口。因此，委员会问题的递推定义式为：,int Comm(int n,int k)if(n n)return 0;if(k=0)return 1;if(n=k)return 1;return Comm(n-1,k-1)+Comm(n-1,k);,例6-7 求两个正整数n和m最大公约数的递推定义式为：,要求：（1）编写求解该问题的递归算法；（2）分析当调用语句为Gcd(30,4)时算法的执行过程和执行结果；（3）分析当调用语句为Gcd(97,5)时算法的执行过程和执行结果；（4）编写求解该问题的循环结构算法。,解：（1）递归算法如下：int Gcd(int n,int m)if(n n)return Gcd(m,n);else return Gcd(m,n%m);（2）调用语句为Gcd(30,4)时，因mn，递归调用Gcd(4,2)；因mn，递归调用Gcd(2,0)；因m=0，到达递归出口，函数最终返回值为n=2，即30和4的最大公约数为2。,（3）调用语句为Gcd(5,97)时，因mn，递归调用Gcd(97,5)；因mn，递归调用Gcd(5,2)；因mn，递归调用Gcd(2,1)；因mn，递归调用Gcd(1,0)；因m=0，到达递归出口，函数最终返回值为n=1，即5和97的最大公约数为1。(4)编写求解该问题的循环结构算法,代码,Fib n:3 f1:1 f2:1 f:2,Fib n:2 f1:1 f2:0 f:1,Fib n:1 f1:f2:f:1,Fib n:1 f1:f2:f:1,Fib n:0 f1:f2:f:0,North China Electric Power University,q(n,m)=,1 m=1,q(n,n)nm,1+q(n,n-1)n=m,q(n,m-1)+q(n-m,m)nm1,0 n1或m1,q(6,6),q(6,5),q(6,4),q(1,5),q(6,3),q(2,4),q(6,2),q(3,3),q(6,1),q(4,2),q(4,1),q(2,2),q(2,1),q(3,2),q(3,1),q(1,2),q(1,1),q(2,2),q(2,1),q(1,1),1+,+,+,+,+,+,+,=,=,1+,1+,1+,=,1,1,1,2,3,4,1,1,1,2,3,7,1,2,2,9,1,1,10,11,q(6,1)=1 q(2,1)=1q(4,1)=1 q(2,2)=2q(2,1)=1 q(2,4)=2q(2,2)=2 q(6,4)=9q(4,2)=3 q(1,1)=1q(6,2)=4 q(1,5)=1q(3,1)=1 q(6,5)=10q(1,1)=1 q(6,6)=11q(1,2)=1q(3,2)=2q(3,3)=3q(6,3)=7,North China Electric Power University,North China Electric Power University,3 递归问题的非递归算法,一般说来，递归过程的实现效率是非常低的，每次递归调用都必须首先做诸如参数替换、环境保护等事情。造成效率低下的另一个重要的原因是大量的重复计算。,Fib(5)的计算过程：Fib(0)计算3次；Fib(1)计算5次；Fib(2)计算3次；Fib(3)计算2次；Fib(4)计算1次。,Fib(n)=Fib(n-1)+Fib(n-2)(n1),North China Electric Power University,Fib(5),Fib(4),Fib(3),Fib(3),Fib(2),Fib(2),Fib(2),Fib(1),Fib(1),Fib(0),Fib(1),Fib(0),Fib(1),Fib(0),Fib(1),将递归算法转化成非递归算法的方法：,1)设计迭代算法：如果一个函数既有递归形式的定义又有非递归的迭代形式的定义，则可以用循环结构设计出迭代算法。一般说来，如果在一个函数或过程中只递归调用它一次，那么它的计算或执行过程可以看成是线性变化的。,n!,(n-1)!,(n-2)!,1!,0!,从顶到底递归,从底到顶返回,North China Electric Power University,int Fact(int n)if(n=0)return 1;else return n*Fact(n-1);int Fact2(int n)x=1;for(i=1;i=n;i+)x=i*x;return x;,以Fibnaocci数列为例，看非递归算法的转化,Fib(5),Fib(4),Fib(3),Fib(3),Fib(2),Fib(2),Fib(1),Fib(2),Fib(1),Fib(1),Fib(0),Fib(1),Fib(0),Fib(1),Fib(0),Fib(5),Fib(4),Fib(3),Fib(2),Fib(0),Fib(1),North China Electric Power University,int Fib2(int n)if(n2)return(n);else int y=0;int x=1;int z;for(int i=2;i=n;i+)z=y;y=x;x=z+y;return(x);,2)消除尾递归：递归调用是最后一步操作,可以用循环结构通过设置一些工作单元，把递归算法转化为非递归算法。开始令工作单元等于外层的实际参数，以后随着循环的执行，不断向里层变化，直到原递归调用的最里层的情况。循环结束后，执行原属于最里层的操作，而后整个算法结束。,North China Electric Power University,例:寻找单链表的最后一个结点并打印其数据域的值的过程search就是一个尾递归过程。,template class link_list Type data;link_list*next;void search(h:link_list)if(h.next=null)couth.data;else search(h.next);void search2(link_list h)p=h;/给工作单元赋值，最外层的实际参数 while(p.next!=null)p=p.next;/向里推进一层 coutp.data;/执行最里层的操作,North China Electric Power University,递归的实现是基于堆栈的，当一个递归问题不容易找到它的迭代算法又不属于尾递归时，通常通过引入一个工作栈保存“返回位置”以实现过程调用一返回控制；这一思想同样适用于递归消除。下面以先根遍历为例，具体讨论如何用工作栈消除递归。首先必须弄清工作栈的作用方式，即弄清怎样用工作栈控制先根遍历的“走向”。二叉链表上的任一X以及它的左XL和右子树XR。假设t是指向结点X的指针.,3)利用堆栈,North China Electric Power University,1.树的先序遍历的非递归实现,North China Electric Power University,由先根遍历的定义可知，当遍历到结点X，即执行preorder(t)时，有三项需顺序完成的工作：访问（根子树的）结点X；遍历XL（与调用preorder(t-lchild)对应）;遍历XR与调用preorder(t-rchild)对应）。其中，与的连接没问题。但与如何连接需要考虑。为了做，必须“知道”XR的“根指针”即结点X的右指针t-rchild:可是X的左子树XL上没有这个指针。因此，应该在做之前便将指针t-rchild保存起来;并当任务完成之后“取出”该指针以便执行任务。在这以后，指针t-rchild就没有保存价值了。对于先根遍历来说，完成了任务也就完成了对以X为根的整个子树的遍历，可以直接退回到X的父结点。,North China Electric Power University,根据以上分析，先根遍历的非递归算法需引入任务栈以保存每个结点的右指针。这样，非递归算法在二叉链表的任一结点X上的主要操作步骤可归纳如下：,访问结点X；结点X的右指针进栈;若XL不空，沿X的左指针遍历XL；从栈中取出X的右指针并将其退栈；若XR不空，沿X右指针遍历XR。,需要特别考虑的是，在二叉链表上，对任一结点X的任何操作都必须借助于指向它的指针的指引才能进行，而这一指针存在于X的父结点的某个指针域中。唯一的例外是根结点，指向它的指针是根指针。为了统一处理这两种情况，可在算法的初始化中先将指针进栈，而在循环体的开头做取栈顶操作。这样，第一次从栈中取出的正是根指针；而以后栈中存储（并取出）的是各个结点的右指针。,North China Electric Power University,综合以上考虑，先根遍历非递归算法的非形式描述如下：根指针进栈；while(栈不空)s=栈顶元素；退栈；while(s!=NULL)/*根或左、右子树不空时继续遍历*/visit(s);s-rchild进栈;/*保存右指针*/s=s-lchild;/*准备遍历左子树*/,North China Electric Power University,voidpreorder1(bitreptrt)/*先根遍历根结点为t的二叉树*/bitreptrstackstacksize;/*工作栈*/inttop;top=0;stacktop=t;/*根指针进栈*/while(top=0)s=stacktop;/*读栈顶元素到S中*/top-;/*退栈*/while(s!=NULL)visit(s);top+;stacktop=s-rchild;/*右指针进栈保存*/s=s-lchild;/*修改s以便继续遍历左子树*/,通过上面的例子可以看出，工作栈在消除递归中的基本作用是提供一种控制机构。在非递归算法执行过程中的某些“关键”时刻，用栈顶元素来“引导”下一步操作的“走向”。为了达到这一目的，必须提前将这些有用的信息进栈保存。在上面的例子中，工作栈保存的是各个结点的右指针，这些指针也就是二叉树上各结点的右子树的根指针。显然，这些根指针正是先根遍历递归算法中包含的一些递归调用的实参；这些实参在非递归算法中若不及时保存就会丢失。因此，递归算法中的调用一返回控制被工作栈的作用所取代，从而将递归算法转换成非递归算法。,North China Electric Power University,2.n!的非递归实现,首先设定一个工作记录栈S,其类型定义如下：#define maxsize 100struct sqlStack int Elemmaxsize;int top;int Fact1(int n)InitStack(S);PushStack(S,n);while(S.ElemS.top 1)PushStack(S,n-1);f=1;while(EmptyStack(S)!=True)f=f*S.ElemS.top;PopStack(S);,int Factorial(int n)if(n=0)return 1;return n*Factorial(n-1);,North China Electric Power University,4 递归方程解的渐近阶的求法,解递归方程：,T(n)=,1 若n=2,2T(n/2)+2 若n2,可以用叠代法来求解，设n=2k，且k为大于1的整数。,T(n)=2T(n/2)+2=2T(2k-1)+2=2(2T(2k-2)+2)+2=22T(k-2)+22+2=2k-1T(2k-(k-1)+2k-1+2k-2+22+2=2k-1T(2)+2k-2=2k-1+2k-2=(3/2)2k-2,代入n=2k，得T(n)=(3/2)n-2,North China Electric Power University,定理：设a,b,c是非负常数，n是c的整幂，则递归方程：,T(n)=,b 若n=1,aT(n/c)+bn 若n1,的解是,T(n)=,O(n)若ac,O(n log2n)若a=c,若ac,证明：因为n是c的整幂，可得,North China Electric Power University,North China Electric Power University,5 生成函数,North China Electric Power University,North China Electric Power University,例2 求斐波那契数列的通项Fib(n)的解析表达式。解 设Fib(n)的生成函数为 G(x)=Fib(0)+Fib(1)x+Fib(2)x2+Fib(n)xn+1)xG(x)=Fib(0)x+Fib(1)x2+Fib(2)x3+Fib(n)xn+1+2)x2 G(x)=Fib(0)x2+Fib(1)x3+Fib(n)xn+2+3)1)-2)-3)得：G(x)(1-x-x2)=Fib(0)+x(Fib(1)-Fib(0)+x2(Fib(2)-Fib(1)-Fib(0)+Fib(0)=1,Fib(1)=1 G(x)(1-x-x2)=x,North China Electric Power University,North China Electric Power University,North China Electric Power University,求一个递归式的非递归表示的一般步骤可概括为：1）设生成函数 H(x)=h1x+h2x2+hnxn+使数列hn与要求解的递归式对应。2）解H(x)为一解析式 H(x)=解析表达式 3）重新展开H(x)H(x)=a1x+a2x2+anxn+4）求出H(x)展开式的通项 H(x)=这里的an就是我们要的递归式的非递归表示。,North China Electric Power University,North China Electric Power University,6 递归树,结点形式,size:表示结点中T的实际参数,nonrec.cost:表示结点的非递归耗费,结点扩展：确定一个不完全结点的子结点和非递归耗费 域的过程。,结点的扩展方法：递归方程中所有含T的项成为它的子结点；2.剩余的项为该结点的非递归耗费域的值。,North China Electric Power University,T(n)=T(n/2)+T(n/2)+n,T(n/2)n/2,T(n/2)n/2,T(n/4)n/4,T(n/4)n/4,T(n/4)n/4,T(n/4)n/4,对于递归树的任意一棵子树，满足下面的关系：,size field of root=nonrec.Costs of expanded nodes,+size fields of incomplete nodes.,通过递归树解递归方程的方法：,1.首先计算递归树中同一层的所有结点的非递归耗费域之和；,2.再将刚才计算出的每一层的非递归耗费域之和求和。,T(n/2)n/2,T(n/2)n/2,T(n/4)n/4,T(n/4)n/4,T(n/4)n/4,T(n/4)n/4,n,n,n,n,(nlogn),North China Electric Power University,T(n-c)1,T(n-c)1,T(n-2c)1,T(n-2c)1,T(n-2c)1,T(n-2c)1,1,2,4,8,(2n/c),T(n)=2T(n-c)+1,North China Electric Power University,