数据结构 递归幻灯片.ppt

《数据结构 递归幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构 递归幻灯片.ppt（41页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构 递归递归第1页，共41页，编辑于2022年，星期六6.1 6.1 什么是递归什么是递归6.1.1 6.1.1 递归的定义递归的定义 在定义一个过程或函数时出现调用本过程或本函数在定义一个过程或函数时出现调用本过程或本函数的成分的成分,称之为称之为递归递归。若调用自身。若调用自身,称之为称之为直接递归直接递归。若过程或函数若过程或函数p p调用过程或函数调用过程或函数q,q,而而q q又调用又调用p,p,称之为称之为间间接递归接递归。如果一个递归过程或递归函数中递归调用语句是最如果一个递归过程或递归函数中递归调用语句是最后一条执行语句后一条执行语句,则称这种递归调用为则称这种递

2、归调用为尾递归尾递归。第2页，共41页，编辑于2022年，星期六例例6.1 以下是求以下是求n!(n为正整数为正整数)的递归函数。的递归函数。int fun(int n)if(n=1)/*语句语句1*/return 1;/*语句语句2*/else/*语句语句3*/return fun(n-1)*n;/*语句语句4*/在在该该函函数数fun(n)求求解解过过程程中中,直直接接调调用用fun(n-1)(语语句句4)自自身身,所所以以它它是是一一个个直直接接递递归归函函数数。又又由由于于递递归归调调用用是是最最后后一一条条语语句句,所以它又属于尾递归。所以它又属于尾递归。第3页，共41页，编辑于20

3、22年，星期六6.1.2 6.1.2 何时使用递归何时使用递归 在以下三种情况下在以下三种情况下,常常要用到递归的方法。常常要用到递归的方法。1.定义是递归的定义是递归的 有许多数学公式、数列等的定义是递归的。例如有许多数学公式、数列等的定义是递归的。例如,求求n!和和Fibonacci数列等。这些问题的求解过程可以将数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。其递归定义直接转化为对应的递归算法。第4页，共41页，编辑于2022年，星期六2.数据结构是递归的数据结构是递归的 有些数据结构是递归的。例如有些数据结构是递归的。例如,第第2章中介绍过的单链章中介绍过的单链表就

4、是一种递归数据结构表就是一种递归数据结构,其结点类型定义如下：其结点类型定义如下：typedef struct LNode ElemType data;struct LNode*next;LinkList;该定义中该定义中,结构体结构体LNode的定义中用到了它自身的定义中用到了它自身,即指针即指针域域next是一种指向自身类型的指针是一种指向自身类型的指针,所以它是一种递归数据所以它是一种递归数据结构。结构。第5页，共41页，编辑于2022年，星期六 对对于于递递归归数数据据结结构构,采采用用递递归归的的方方法法编编写写算算法法既既方方便便又又有有效效。例例如如,求求一一个个不不带带头头结结

5、点点的的单单链链表表head的的所所有有data域域(假设为假设为int型型)之和的递归算法如下：之和的递归算法如下：int Sum(LinkList*head)if(head=NULL)return 0;else return(head-data+Sum(head-next);第6页，共41页，编辑于2022年，星期六3.问题的求解方法是递归的问题的求解方法是递归的 有有些些问问题题的的解解法法是是递递归归的的,典典型型的的有有Hanoi问问题题求求解解,该该问问题题描描述述是是：设设有有3个个分分别别命命名名为为X,Y和和Z的的塔塔座座,在在塔塔座座X上上有有n个个直直径径各各不不相相同同

6、,从从小小到到大大依依次次编编号号为为1,2,n的的盘盘片片,现现要要求求将将X塔塔座座上上的的n个个盘盘片片移移到到塔塔座座Z上上并并仍仍按按同同样样顺顺序序叠叠放放,盘盘片片移移动动时时必必须须遵遵守守以以下下规规则则：每每次次只只能能移移动动一一个个盘盘片片；盘盘片片可可以以插插在在X,Y和和Z中中任任一一塔塔座座；任任何何时时候候都都不不能能将将一一个个较较大大的的盘盘片片放放在在较较小小的的盘盘片片上上。设设计计递归求解算法递归求解算法,并将其转换为非递归算法。并将其转换为非递归算法。设设Hanoi(n,x,y,z)表表示示将将n个个盘盘片片从从x通通过过y移移动动到到z上上,递递归

7、分解的过程是：归分解的过程是：第7页，共41页，编辑于2022年，星期六Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)；move(n,x,z):将第将第n个圆盘从个圆盘从x移到移到z；Hanoi(n-1,y,x,z)第8页，共41页，编辑于2022年，星期六6.1.3 6.1.3 递归模型递归模型 递递归归模模型型是是递递归归算算法法的的抽抽象象,它它反反映映一一个个递递归归问问题题的的递递归归结构结构,例如例如,前面的递归算法对应的递归模型如下：前面的递归算法对应的递归模型如下：fun(1)=1 (1)fun(n)=n*fun(n-1)n1 (2)其其中中,第第一一个个式式子子

8、给给出出了了递递归归的的终终止止条条件件,第第二二个个式式子子给给出出了了fun(n)的的值值与与fun(n-1)的的值值之之间间的的关关系系,我我们们把把第第一一个个式式子子称为称为递归出口递归出口,把第二个式子称为把第二个式子称为递归体递归体。第9页，共41页，编辑于2022年，星期六 一般地一般地,一个递归模型是由递归出口和递归体两部分组成一个递归模型是由递归出口和递归体两部分组成,前者确定递归到何时结束前者确定递归到何时结束,后者确定递归求解时的递推关系。后者确定递归求解时的递推关系。递归出口的一般格式如下：递归出口的一般格式如下：f(s1)=m1 (6.1)这这里里的的s1与与m1均

9、均为为常常量量,有有些些递递归归问问题题可可能能有有几几个个递递归归出出口口。递归体的一般格式如下：递归体的一般格式如下：f(sn+1)=g(f(si),f(si+1),f(sn),cj,cj+1,cm)(6.2)其其中中,n,i,j,m均均为为正正整整数数。这这里里的的sn+1是是一一个个递递归归“大大问问题题”,si,si+1,sn为为递递归归“小小问问题题”,cj,cj+1,cm是是若若干干个个可可以以直直接接(用用非非递递归归方方法法)解解决决的的问问题题,g是是一一个个非非递递归归函函数数,可可以以直接求值。直接求值。第10页，共41页，编辑于2022年，星期六 实际上实际上,递归思

10、路是把一个不能或不好直接求解的递归思路是把一个不能或不好直接求解的“大大问题问题”转化成一个或几个转化成一个或几个“小问题小问题”来解决来解决,再把这些再把这些“小小问题问题”进一步分解成更小的进一步分解成更小的“小问题小问题”来解决来解决,如此分解如此分解,直至每个直至每个“小问题小问题”都可以直接解决都可以直接解决(此时分解到递归出口此时分解到递归出口)。但递归分解不是随意的分解。但递归分解不是随意的分解,递归分解要保证递归分解要保证“大问题大问题”与与“小问题小问题”相似相似,即求解过程与环境都相似。即求解过程与环境都相似。第11页，共41页，编辑于2022年，星期六为了讨论方便为了讨论

11、方便,简化上述递归模型为：简化上述递归模型为：f(s1)=m1(6.3)f(sn)=g(f(sn-1),c)(6.4)求求f(sn)的分解过程如下：的分解过程如下：f(sn)f(sn-1)f(s2)f(s1)第12页，共41页，编辑于2022年，星期六 一一旦旦遇遇到到递递归归出出口口,分分解解过过程程结结束束,开开始始求求值值过过程程,所所以以分分解解过过程程是是“量量变变”过过程程,即即原原来来的的“大大问问题题”在在慢慢慢慢变变小小,但但尚尚未未解解决决,遇遇到到递递归归出出口口后后,便便发发生生了了“质质变变”,即即原原递归问题便转化成直接问题。上面的求值过程如下：递归问题便转化成直接

12、问题。上面的求值过程如下：f(s1)=m1 f(s2)=g(f(s1),c1)f(s3)=g(f(s2),c2)f(sn)=g(f(sn-1),cn-1)第13页，共41页，编辑于2022年，星期六 这样这样f(sn)便计算出来了便计算出来了,因此因此,递归的执行过程由递归的执行过程由分解和求值两部分构成。分解和求值两部分构成。第14页，共41页，编辑于2022年，星期六求解求解fun(5)的过程如下：的过程如下：第15页，共41页，编辑于2022年，星期六6.2 6.2 递归算法的设计递归算法的设计 递递归归的的求求解解的的过过程程均均有有这这样样的的特特征征：先先将将整整个个问问题题划划分

13、分为为若若干干个个子子问问题题,通通过过分分别别求求解解子子问问题题,最最后后获获得得整整个个问问题题的的解解。而而这这些些子子问问题题具具有有与与原原问问题题相相同同的的求求解解方方法法,于于是是可可以以再再将将它它们们划划分分成成若若干干个个子子问问题题,分分别别求求解解,如如此此反反复复进进行行,直直到到不不能能再再划划分分成成子子问问题题,或或已已经经可可以以求求解解为为止止。这这种种自自上上而而下下将将问问题题分分解解、求求解解,再再自自上上而而下下引引用用、合合并并,求求出出最最后后解解答答的的过过程程称称为为递递归求解过程。这是一种分而治之的算法设计方法。归求解过程。这是一种分而

14、治之的算法设计方法。递递归归算算法法设设计计先先要要给给出出递递归归模模型型,再再转转换换成成对对应应的的C/C+语言函数。语言函数。第16页，共41页，编辑于2022年，星期六 递归设计的步骤如下：递归设计的步骤如下：(1)对对原原问问题题f(s)进进行行分分析析,假假设设出出合合理理的的“较较小小问问题题”f(s)(与数学归纳法中假设与数学归纳法中假设n=k-1时等式成立相似时等式成立相似)；(2)假假设设f(s)是是可可解解的的,在在此此基基础础上上确确定定f(s)的的解解,即即给给出出f(s)与与f(s)之之间间的的关关系系(与与数数学学归归纳纳法法中中求求证证n=k时时等等式式成成立

15、立的过程相似的过程相似)；(3)确定一个特定情况确定一个特定情况(如如f(1)或或f(0)的解的解,由此作为递归出口由此作为递归出口(与数学归纳法中求证与数学归纳法中求证n=1时等式成立相似时等式成立相似)。第17页，共41页，编辑于2022年，星期六 例如例如,采用递归算法求实数数组采用递归算法求实数数组A0.n-1中的最小值。中的最小值。假设假设f(A,i)函数求数组元素函数求数组元素A0Ai中的最小值。中的最小值。当当i=0时时,有有f(A,i)=A0；假假设设f(A,i-1)已已求求出出,则则f(A,i)=MIN(f(A,i-1),Ai),其其中中MIN()为求两个值较小值函数。因此得

16、到如下递归模型：为求两个值较小值函数。因此得到如下递归模型：A0 当当i=0时时 f(A,i)=MIN(f(A,i-1),Ai)其他情况其他情况第18页，共41页，编辑于2022年，星期六由此得到如下递归求解算法：由此得到如下递归求解算法：float f(float A,int i)float m;if(i=0)return A0;else m=f(A,i-1);if(mAi)return Ai;else return m;第19页，共41页，编辑于2022年，星期六例求例求1，2，n的全排列。的全排列。解：用数组解：用数组a存放存放n个不同字符的字符串，个不同字符的字符串，设设f(a,k,n

17、)为为a0.k的的所有字符的全排序。所有字符的全排序。则则f(a,k-1,n)为为a0.k-1的所有字符的全排序。的所有字符的全排序。假设假设f(a,k-1,n)可求，对于可求，对于ak位置，可以取位置，可以取a0.k任何之值，任何之值，再组合再组合f(a,k-1,n)，则得到，则得到f(a,k,n)递归模型为：递归模型为：f(a,k,n)：输出：输出a 当当k=0时时 f(a,k,n)：ak位置取位置取a0.k任何之值任何之值,其他情况其他情况 并组合并组合f(a,k-1,n)的结果的结果;第20页，共41页，编辑于2022年，星期六void f(char str,int k,int n)i

18、nt i,j;char tmp;if(k=0)for(j=0;jn;j+)printf(%c,aj);printf(n);else for(i=0;i=k;i+)akaj;f(a,k-1,n);akai 第21页，共41页，编辑于2022年，星期六例采用递归算法求解皇后问题：在例采用递归算法求解皇后问题：在nn的方格的方格棋盘上，放置棋盘上，放置n个皇后，要求每个皇后不同行、不同个皇后，要求每个皇后不同行、不同列、不同左右对角线。列、不同左右对角线。解：解：设设place(k,n)表示在前面表示在前面1，k-1个皇后放置好个皇后放置好后，用于放置后，用于放置k，n的皇后。求解皇后问题的递归模的

19、皇后。求解皇后问题的递归模型如下：型如下：place(i,n)：n个皇后放置完毕，输出解个皇后放置完毕，输出解若若i=n place(k,n)：对于第：对于第k列的每个合适的位置列的每个合适的位置i,在其上放置一个皇后在其上放置一个皇后;place(k+1,n);其他情况其他情况第22页，共41页，编辑于2022年，星期六6.3 6.3 递归算法到非递归算法的转换递归算法到非递归算法的转换 递递归归算算法法有有两两个个基基本本特特性性：一一是是递递归归算算法法是是一一种种分分而而治治之之的的、把把复复杂杂问问题题分分解解为为简简单单问问题题的的求求解解问问题题方方法法,对对求求解解某某些些复复

20、杂杂问问题题,递递归归算算法法分分析析问问题题的的方方法法是是十十分分有有效效的的；二二是是递递归归算算法法的的时时间间效效率率通通常常比比较较差差。因因此此,对对求求解解某某些些问问题题时时,我我们们希希望望用用递递归归算算法法分分析析问问题题,用用非非递递归归算算法法具具体体求求解解问问题题。这这就就需需要要把把递递归归算算法法转转换换为为非非递递归归算算法。法。第23页，共41页，编辑于2022年，星期六把递归算法转化为非递归算法有如下三种基本方法：把递归算法转化为非递归算法有如下三种基本方法：(1)对对于于尾尾递递归归和和单单向向递递归归的的算算法法,可可用用循循环环结结构构的的算算法

21、法替代。替代。(2)自自己己用用栈栈模模拟拟系系统统的的运运行行时时栈栈,通通过过分分析析只只保保存存必必须须保保存存的信息的信息,从而用非递归算法替代递归算法。从而用非递归算法替代递归算法。(3)利利用用栈栈保保存存参参数数,由由于于栈栈的的后后进进先先出出特特性性吻吻合合递递归归算算法的执行过程法的执行过程,因而可以用非递归算法替代递归算法。因而可以用非递归算法替代递归算法。本节讨论第本节讨论第(1)种和第种和第(2)种情况的递归算法转化为非递种情况的递归算法转化为非递归算法的问题归算法的问题,前者是一种是直接转化法前者是一种是直接转化法,不需要使用栈不需要使用栈,后后者是间接转化法者是间

22、接转化法,需要使用栈。第需要使用栈。第(3)种情况也需要使用栈种情况也需要使用栈,但因具体情况而异但因具体情况而异,例如例如,在第在第7章的例章的例7.6就是这种情况的一就是这种情况的一个例子。个例子。第24页，共41页，编辑于2022年，星期六6.3.1 6.3.1 尾递归和单向递归的消除尾递归和单向递归的消除 采采用用循循环环结结构构消消除除尾尾递递归归和和单单向向递递归归。求求解解Fibonacci数列的算法如下：数列的算法如下：int Fib(int n)int i,f1,f2,f3;if(n=1|n=2)return(n);f1=1;f2=2;for(i=3;i-1)/*栈不空时循环

23、栈不空时循环*/if(Sttop.tag=1)/*未计算出栈顶元素的未计算出栈顶元素的f值值*/if(Sttop.n=1)/*(1)式式*/Sttop.f=1;Sttop.tag=0;else/*(2)式分解过程式分解过程*/top+;Sttop.n=Sttop-1.n-1;Sttop.tag=1;else if(Sttop.tag=0)/*已计算出已计算出f值值*/Sttop-1.f=Sttop-1.n*Sttop.f;/*(2)式求值过程式求值过程*/Sttop-1.tag=0;top-;第31页，共41页，编辑于2022年，星期六 if(top=0&Sttop.tag=0)/*栈中只有一

24、个已求出栈中只有一个已求出f的元素的元素时退出循环时退出循环*/break;return(Sttop.f);第32页，共41页，编辑于2022年，星期六Ackerman函数的定义如下：函数的定义如下：akm(m,n)=n+1 m=0akm(m-1,1)m0,n=0akm(m-1,akm(m,n-1)m0,n 0设计对应的非递归算法。设计对应的非递归算法。第33页，共41页，编辑于2022年，星期六计算计算akm(2,1)的递归调用过程树的递归调用过程树 第34页，共41页，编辑于2022年，星期六2等价关系 等价关系是指等价关系是指“大问题大问题”的求解过程转化为的求解过程转化为“小小问题问题

25、”求解而得到的，它们之间不是值的相等关系，求解而得到的，它们之间不是值的相等关系，而是解的等价关系。而是解的等价关系。例如，求梵塔问题对应的递归模型就是等价关系，也例如，求梵塔问题对应的递归模型就是等价关系，也就是说，就是说，Hanoi(n,x,y,z)与与Hanoi(n-1,x,z,y)、move(n,x,z)和和Hanoi(n-1,y,x,z)是等价的。该问题完整的递归模型如下：是等价的。该问题完整的递归模型如下：Hanoi(n,x,y,z)直接将直接将x上的盘片从上的盘片从x移动到移动到z上上 当当n=1时时（1）Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)；将第将第n个

26、圆盘从个圆盘从x移动到移动到z上；上；Hanoi(n-1,y,x,z)当当n1时时（2）第35页，共41页，编辑于2022年，星期六 对应的非递归求解过程如下：对应的非递归求解过程如下：定义一个栈定义一个栈;将初始问题进栈将初始问题进栈;while(栈不空栈不空)if(栈顶元素的栈顶元素的tag=1)/*不能直接操作不能直接操作*/将栈中元素出栈将栈中元素出栈;将将Hanoi(n-1,y,x,z)进栈进栈;将将“将第将第n个圆盘从个圆盘从x移动到移动到z上上”操作进栈操作进栈;将将Hanoi(n-1,x,z,y)进栈进栈;if(栈顶元素满足递归出口条件栈顶元素满足递归出口条件)直接操作并置直接

27、操作并置tag=0;注意：上述过程中进栈的次序与注意：上述过程中进栈的次序与(2)中三步的求解次序正好相反，这中三步的求解次序正好相反，这是由于是由于Hanoi问题和栈的特点决定的。问题和栈的特点决定的。第36页，共41页，编辑于2022年，星期六非递归算法非递归算法Hanoi()如下：如下：void Hanoi1(int n,char x,char y,char z)int n1,x1,y1,z1;if(n-1)/*栈不空循环栈不空循环*/if(Sttop.tag=1&Sttop.n1)/*不能直接操作不能直接操作*/n1=Sttop.n;/*退栈退栈hanoi(n,x,y,z)*/x1=S

28、ttop.x;y1=Sttop.y;z1=Sttop.z;top-;top+;/*将将Hanoi(n-1,y,x,z)进栈进栈*/Sttop.n=n1-1;Sttop.x=y1;Sttop.y=x1;Sttop.z=z1;if(n1-1=1)/*只有一个盘片时直接操作只有一个盘片时直接操作*/Sttop.tag=0;elseSttop.tag=1;top+;/*将第将第n个圆盘从个圆盘从x移到移到z;*/Sttop.n=n1;Sttop.x=x1;Sttop.z=z1;Sttop.tag=0;第38页，共41页，编辑于2022年，星期六 top+;/*将将Hanoi(n-1,x,z,y)进栈进

29、栈*/Sttop.n=n1-1;Sttop.x=x1;Sttop.y=z1;Sttop.z=y1;if(n1-1=1)/*只有一个盘片时直接操作只有一个盘片时直接操作*/Sttop.tag=0;elseSttop.tag=1;else if(Sttop.tag=0)/*当可以直接操作时当可以直接操作时*/printf(t将第将第%d个盘片从个盘片从%c移动到移动到%cn,Sttop.n,Sttop.x,Sttop.z);top-;/*移动盘片后退栈移动盘片后退栈*/第39页，共41页，编辑于2022年，星期六本章小结本章小结 本章基本学习要点如下：本章基本学习要点如下：(1)理解递归的定义和递归模型。理解递归的定义和递归模型。(2)重点掌握递归的执行过程。重点掌握递归的执行过程。(3)掌握递归设计的一般方法。掌握递归设计的一般方法。(4)掌握消除递归的基本方法。掌握消除递归的基本方法。(5)灵活运用递归算法解决一些较复杂应用问题。灵活运用递归算法解决一些较复杂应用问题。第40页，共41页，编辑于2022年，星期六练习题练习题6 习题习题1和和2。第41页，共41页，编辑于2022年，星期六