最新【考研计算机专业课】武汉大学数据结构PPT课件 第6章递归(共57张PPT课件).pptx

《最新【考研计算机专业课】武汉大学数据结构PPT课件 第6章递归(共57张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】武汉大学数据结构PPT课件 第6章递归(共57张PPT课件).pptx（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章章 递归递归 6.1 什么什么(shn me)是递归是递归6.2 递归算法递归算法(sun f)的设计的设计第一页，共五十七页。6.1 什么是递归什么是递归6.1.1 递归的定义递归的定义 在定义一个过程或函数时出现调用本过程或本函数的成分在定义一个过程或函数时出现调用本过程或本函数的成分, ,称之为递归。若调用自身称之为递归。若调用自身, ,称之为称之为直接递归直接递归。若过程或函数。若过程或函数p p调用调用过程或函数过程或函数q,q,而而q q又调用又调用p,p,称之为称之为间接递归间接递归。 如果一个递归过程或递归函数中递归调用语句是最后如果一个递归过程或递归函数中递归调用语句

2、是最后(zuhu)(zuhu)一条执行语句一条执行语句, ,则称这种递归调用为则称这种递归调用为尾递归尾递归。第二页，共五十七页。 例如，以下是求例如，以下是求n!(n为正整数为正整数)的递归函数。的递归函数。 int fun(int n) if (n=1) /语句语句1 return 1;/语句语句2 else /语句语句3 return fun(n-1)*n; /语句语句4 在该函数在该函数fun(n)求解过程求解过程(guchng)中中,直接调用直接调用fun(n-1)(语句语句4)自自身身,所以它是一个直接递归函数。又由于递归调用是最后一条语句所以它是一个直接递归函数。又由于递归调用是

3、最后一条语句,所以它又属于所以它又属于尾递归尾递归。第三页，共五十七页。6.1.2 何时使用递归何时使用递归 在以下三种情况下在以下三种情况下,常常要用到递归的方法。常常要用到递归的方法。 1. 定义是递归的定义是递归的 有许多数学公式、数列等的定义是递归的。例如有许多数学公式、数列等的定义是递归的。例如,求求n!和和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转数列等。这些问题的求解过程可以将其递归定义直接转化化(zhunhu)为对应的递归算法。为对应的递归算法。 思考题：指出思考题：指出(zh ch)正整数的定正整数的定义。义。第四页，共五十七页。2. 数据结构是递归的

4、数据结构是递归的 有些数据结构是递归的。例如有些数据结构是递归的。例如,第第2章中介绍过的单链表就是一种章中介绍过的单链表就是一种递归数据结构递归数据结构,其结点类型定义如下：其结点类型定义如下： typedef struct LNode ElemType data; struct LNode *next; LinkList; 该定义中该定义中,结构结构(jigu)体体LNode的定义中用到了它自身的定义中用到了它自身,即指针域即指针域next是一种指向自身类型的指针是一种指向自身类型的指针,所以它是一种递归数据结构所以它是一种递归数据结构(jigu)。 为什么可以这样递归定为什么可以这样递归

5、定义义(dngy)类型类型第五页，共五十七页。 对于递归数据结构对于递归数据结构,采用递归的方法采用递归的方法(fngf)编写算法既方便又有效。例如编写算法既方便又有效。例如,求一个不带头结点的单链表求一个不带头结点的单链表L的所有的所有data域域(假设为假设为int型型)之和的递归算法如之和的递归算法如下：下： int Sum(LinkList *L) if (L=NULL) return 0; else return(L-data+Sum(L-next); 第六页，共五十七页。3. 问题的求解方法是递归的问题的求解方法是递归的 有些问题的解法是递归的有些问题的解法是递归的,典型的有典型的

6、有Hanoi问题求解问题求解,该问题描述是：设该问题描述是：设有有3个分别命名为个分别命名为X,Y和和Z的塔座的塔座,在塔座在塔座X上有上有n个直径各不相同个直径各不相同,从小到大从小到大依次编号为依次编号为1,2,n的盘片的盘片,现要求现要求(yoqi)将将X塔座上的塔座上的n个盘片移到塔座个盘片移到塔座Z上上并仍按同样顺序叠放并仍按同样顺序叠放,盘片移动时必须遵守以下规则：每次只能移动一个盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在盘片；盘片可以插在X,Y和和Z中任一塔座；任何时候都不能将一个较大的中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算

7、法盘片放在较小的盘片上。设计递归求解算法,并将其转换为非递归算法。并将其转换为非递归算法。 设设Hanoi(n,x,y,z)表示将表示将n个盘片从个盘片从x通过通过y移动到移动到z上上,递归分解的过程递归分解的过程是：是：第七页，共五十七页。Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)；move(n,x,z):将第将第n个圆盘个圆盘(yun pn)从从x移移到到z；Hanoi(n-1,y,x,z)第八页，共五十七页。6.1.3 递归模型递归模型 递归模型是递归算法的抽象递归模型是递归算法的抽象,它反映一个递归问题它反映一个递归问题(wnt)的递归结构的递归结构,例如例如,前面的

8、递归算法对应的递归模型如下：前面的递归算法对应的递归模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 其中其中,第一个式子给出了递归的终止条件第一个式子给出了递归的终止条件,第二个式子给出了第二个式子给出了fun(n)的的值与值与fun(n-1)的值之间的关系的值之间的关系,我们把第一个式子称为我们把第一个式子称为递归出口递归出口,把第二个把第二个式子称为式子称为递归体递归体。第九页，共五十七页。 一般地一般地,一个递归模型是由递归出口和递归体两部分组成一个递归模型是由递归出口和递归体两部分组成,前者确定前者确定(qudng)递归到何时结束递归到何时结束,

9、后者确定后者确定(qudng)递归求解时的递推关系。递归出口的一般格递归求解时的递推关系。递归出口的一般格式如下：式如下： f(s1)=m1 (6.1) 这里的这里的s1与与m1均为常量均为常量,有些递归问题可能有几个递归出口。递有些递归问题可能有几个递归出口。递归体的一般格式如下：归体的一般格式如下： 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是若干个可以

10、直接是若干个可以直接(用非用非递归方法递归方法)解决的问题解决的问题,g是一个非递归函数是一个非递归函数,可以直接求值。可以直接求值。第十页，共五十七页。 递归思路是：递归思路是：把一个不能或不好直接求解把一个不能或不好直接求解(qi ji)的的“大问题大问题”转化成一个或几个转化成一个或几个“小小问题问题”来解决；来解决；再把这些再把这些“小问题小问题”进一步分解成更小的进一步分解成更小的“小问题小问题”来解决；来解决；如此分解如此分解,直至每个直至每个“小问题小问题”都可以直接解决都可以直接解决(此时分解到递归出口此时分解到递归出口)。但递归分解不是随意的分解但递归分解不是随意的分解,递归

11、分解要保证递归分解要保证“大问题大问题”与与“小问题小问题”相似相似,即求解过程与环境都相似。即求解过程与环境都相似。 第十一页，共五十七页。为了讨论方便为了讨论方便(fngbin),简化上述递归模型为：简化上述递归模型为： f(s1)=m1(6.3) f(sn)=g(f(sn-1),cn-1)(6.4)求求f(sn)的分解过程如下：的分解过程如下： f(sn) f(sn-1) f(s2) f(s1)第十二页，共五十七页。 一旦遇到递归出口一旦遇到递归出口,分解过程结束分解过程结束(jish),开始求值过程开始求值过程,所以分解过所以分解过程是程是“量变量变”过程过程,即原来的即原来的“大问题

12、大问题”在慢慢变小在慢慢变小,但尚未解决但尚未解决,遇遇到递归出口后到递归出口后,便发生了便发生了“质变质变”,即原递归问题便转化成直接问题。即原递归问题便转化成直接问题。上面的求值过程如下：上面的求值过程如下： f(s1)=m1 f(s2)=g(f(s1),c1) f(s3)=g(f(s2),c2) f(sn)=g(f(sn-1),cn-1) 第十三页，共五十七页。 这样这样f(sn)便计算出来了便计算出来了,因此因此,递归的执行过程递归的执行过程(guchng)由分解由分解和求值两部分构成。和求值两部分构成。 第十四页，共五十七页。 fun(5) d1:fun(4) d2:fun(3) d

13、3:fun(2) d4:fun(1) 返回 1 fun(2)=2 fun(3)=6 fun(4)=24 fun(5)=120 求解求解(qi ji)fun(5)的过程如下：的过程如下：第十五页，共五十七页。F(1)=0F(2)=1F(n)=F(n-1)+F(n-2) n=2F(5)F(4)F(3)F(2)F(1)F(1)F(0)F(2)F(1)F(0)F(3)F(2)F(1)F(1)F(0)递归树递归树第十六页，共五十七页。思考题：思考题：递归的本质递归的本质(bnzh)是什么？是什么？第十七页，共五十七页。6.2 递归算法的设计递归算法的设计 递归的求解的过程均有这样的特征：递归的求解的过程

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

15、出最后解答的过程称为递归求解过程。这是一种分分而治之而治之的算法设计方法。的算法设计方法。 递归算法设计先要给出递归模型递归算法设计先要给出递归模型,再转换成对应的再转换成对应的C/C+语言函语言函数。数。第十八页，共五十七页。 求递归模型的步骤如下：求递归模型的步骤如下： （1）对原问题）对原问题(wnt)f(s)进行分析进行分析,假设出合理的假设出合理的“较小问题较小问题(wnt)”f(s)(与数学归纳法中假设与数学归纳法中假设n=k-1时等式成立相似时等式成立相似)； （2）假设）假设f(s)是可解的是可解的,在此基础上确定在此基础上确定f(s)的解的解,即给出即给出f(s)与与f(s)

16、之间的关之间的关系系(与数学归纳法中求证与数学归纳法中求证n=k时等式成立的过程相似时等式成立的过程相似)； （3）确定一个特定情况）确定一个特定情况(如如f(1)或或f(0)的解的解,由此作为递归出口由此作为递归出口(与数学归与数学归纳法中求证纳法中求证n=1时等式成立相似时等式成立相似)。第十九页，共五十七页。 例如例如,采用递归算法求实数数组采用递归算法求实数数组A0.n-1中的最小值。中的最小值。 假设假设f(A,i)函数求数组元素函数求数组元素A0Ai中的最小值。中的最小值。 当当i=0时时,有有f(A,i)=A0； 假设假设f(A,i-1)已求出已求出,则则f(A,i)=MIN(f

17、(A,i-1),Ai),其中其中MIN()为求两个值较为求两个值较小值函数。因此得到如下小值函数。因此得到如下(rxi)递归模型：递归模型： f(A,i)=A0当当i=0时时f(A,i)= MIN(f(A,i-1),Ai) 其他其他(qt)情情况况第二十页，共五十七页。 由此得到如下递归求解由此得到如下递归求解(qi ji)算法：算法： 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; 第二十一页，共五十七页。例如，设计不带头例如，设计不

18、带头(di tu)结点的单链表的相关递归算法结点的单链表的相关递归算法a1a2an.Lf(L)：大问题：大问题(wnt)f(L- -next)：小问题：小问题(wnt)为什么在设计单链表的递归算法时不带头结点？为什么在设计单链表的递归算法时不带头结点？第二十二页，共五十七页。（1）求单链表中数据）求单链表中数据(shj)结点个结点个数数递归模型递归模型(mxng)如下：如下：f(L)=0当当L=NULLf(L)=f(L- -next)+1其他其他(qt)情况情况int count(Node *L) if (L=NULL) return 0; else return count(L-next)+

19、1;递归算法如下：递归算法如下：第二十三页，共五十七页。（2）正向）正向(zhn xin)显示以显示以L为首节点指针的单链表的所有节点值为首节点指针的单链表的所有节点值递归模型递归模型(mxng)如下：如下：f(L)不做任何事件不做任何事件当当L=NULLf(L)输出输出(shch)L- -data;f(L- -next)其他其他情况情况void traverse(Node *L)if (L=NULL) return; printf(%d ,L-data); traverse(L-next);递归算法如下：递归算法如下：第二十四页，共五十七页。（3）反向显示以）反向显示以L为首为首(wishu

20、)节点指针的单链表的所有节点值节点指针的单链表的所有节点值递归模型递归模型(mxng)如下：如下：f(L)不做任何事件不做任何事件当当L=NULLf(L)f(L- -next);输出输出L-data;其他其他(qt)情况情况void traverseR(Node *L)if (L=NULL) return; traverseR(L-next); printf(%d ,L-data);递归算法如下：递归算法如下：第二十五页，共五十七页。（4）删除以）删除以L为首节点为首节点(ji din)指针的单链表中值为指针的单链表中值为x的第一个节点的第一个节点(ji din)递归模型递归模型(mxng)如

21、下：如下：f(L,x)不做任何事件不做任何事件当当L=NULLf(L,x) 删除删除(shnch)L所指结点所指结点 当当L- -data=xf(L,x)f(L- -next,x)其他情况其他情况void del(Node *&L,ElemType x) Node *t; if (L=NULL) return; if (L-data=x) t=L; L=L-next; free(t); return; else del(L-next,x);递归算法如下：递归算法如下：第二十六页，共五十七页。（5）删除以）删除以L为首为首(wishu)节点指针的单链表中值为节点指针的单链表中值为x的所有节点的所

22、有节点递归模型递归模型(mxng)如下：如下：f(L,x)不做任何事件不做任何事件(shjin)当当L=NULLf(L,x) 删除删除L所指结点所指结点;f(L-next,x)当当L- -data=xf(L,x) f(L- -next,x)其他情况其他情况void delall(Node *&L,ElemType x) Node *t; if (L=NULL) return; if (L-data=x) t=L; L=L-next; free(t); delall(L-next,x);递归算法如下：递归算法如下：第二十七页，共五十七页。（6）输出）输出(shch)以以L为首节点指针的单链表中最

23、大节点值为首节点指针的单链表中最大节点值递归模型递归模型(mxng)如下：如下：f(L)=L- -data当当L中只有一个中只有一个(y )结点结点f(L)=MAX(f(L- -next),L- -data)其他情况其他情况ElemType maxv(Node *L) ElemType m; if (L-next=NULL) return L-data; m=maxv(L-next); if (mL-data) return m; else return L-data;递归算法如下：递归算法如下：第二十八页，共五十七页。（7）输出）输出(shch)以以L为首节点指针的单链表中最小节点值。为首节

24、点指针的单链表中最小节点值。递归模型递归模型(mxng)如下：如下：f(L)=L- -data当当L中只有一个结点中只有一个结点(ji din)f(L)=MIN(f(L- -next),L- -data)其他情况其他情况ElemType minv(Node *L) ElemType m; if (L-next=NULL) return L-data; m=minv(L-next); if (mL-data) return L-data; else return m;递归算法如下：递归算法如下：第二十九页，共五十七页。（8）释放）释放L为首节点为首节点(ji din)指针的单链表的所有节点指针的

25、单链表的所有节点(ji din)递归模型递归模型(mxng)如下：如下：f(L)不做任何不做任何(rnh)事件事件当当L=NULLf(L)f(L- -next);释放释放L所指结点所指结点; 其他情况其他情况void Destroy(Node *L)if (L=NULL) return; Destroy(L-next); free(L);递归算法如下：递归算法如下：第三十页，共五十七页。 例如，求例如，求1，2，n的全排列。的全排列。设设a是含是含n个不同字符的字符串，个不同字符的字符串，f(a,k-1,n)为为a0.k-1的所有字符的的所有字符的全排序全排序(pi x)，f(a,k,n)为为

26、a0.k的所有字符的全排序。假设的所有字符的全排序。假设f(a,k-1,n)可可求，对于求，对于ak位置，可以取位置，可以取a0.k任何之值，再组合任何之值，再组合f(a,k-1,n)，则得，则得到到f(a,k,n)递归模型为：递归模型为： a0 a1 ak-1 ak an-1 f(a,k-1,n) f(a,k,n) f(a,k,n)：输出：输出(shch)a 当当k=0时时f(a,k,n)：ak位置取位置取a0.k任何之值任何之值, 其他情况其他情况 并组合并组合f(a,k-1,n)的结果的结果;此位置此位置(wi zhi)可以取可以取a0ak中任何值，但中任何值，但不重复！不重复！第三十一

27、页，共五十七页。例如例如(lr)，求，求a=“123”的全排列（下标为的全排列（下标为02），），f(a,2,3) ：位置位置2：此处放此处放1（即（即1和和3交换交换(jiohun)），），32的全排列有的全排列有23、32，输出输出231、321此处放此处放2（即（即2和和3交换），交换），13的全排列有的全排列有13、31，输出输出312、132此处放此处放3（即（即3和和3交换），交换），12的全排列有的全排列有21、12， 输出输出213、123位置位置1和位置和位置0的求法类似的求法类似(li s)，属，属“小问题小问题”。第三十二页，共五十七页。void f(char a,int

28、 k,int n) int i,j; char tmp; if (k=0) for (j=0;jn;j+) printf(%c,aj); printf(n); else for (i=0;i=k;i+) akai; f(a,k-1,n); akai void main() char a=123; f(a,2,3);输出输出(shch)结果：结果：231321312132213123第三十三页，共五十七页。 设计一个程序求解组合问题：从自然数设计一个程序求解组合问题：从自然数1n中任取中任取r个数的所有组个数的所有组合。合。 设设comb(a,m,k)为从为从1m中任取中任取k个数的所有组合（每

29、个组合放个数的所有组合（每个组合放在数组在数组a中）。当组合的第中）。当组合的第1个数字选定后，其后的数字是从余下个数字选定后，其后的数字是从余下(yxi)的的m- -1个数中取个数中取k- -1个数的组合。求解组合问题的递归模型如下：个数的组合。求解组合问题的递归模型如下：comb(a,m,k)输出产生输出产生(chnshng)的解的解若若k=1comb(a,m,k)for (i=m;i=k;i-);其他情况其他情况 ak- -1=i;comb(a,i- -1,k- -1);k个元素个元素(yun s)的组合结果放在的组合结果放在a0.k- -1中。中。1 2 3 . k k+1 . m-

30、-1 mcomb(a,m,k)ak-1comb(a,m- -1,k- -1)a0.k-2ak-1可取可取km的的任何值任何值第三十四页，共五十七页。求求f(a,5,3)：m=5，k=3，i=5 3：i=5：a2=5，f(a,4,2)i=4：a2=4，f(a,3,2)i=3：a2=3，f(a,2,2)求求f(a,4,2)：m=4，k=2，i=42i=4:a1=4,f(a,3,1)i=3:a1=3,f(a,2,1)i=4:a1=2,f(a,1,1)求求f(a,3,1)：m=3，k=1，i=31i=3:a0=3,输出输出(shch)a即即543i=2:a0=2,输出输出a即即542i=1:a0=1,

31、输出输出a即即541.a0a1a2只取只取53中中值值(zhn zh)之一之一第三十五页，共五十七页。#include #define MaxSize 10int m,k;/全局变量全局变量void print(int a)/输出一个输出一个(y )组合组合 int j; for (j=k-1;j=0;j-) printf(%d ,aj); printf(n);第三十六页，共五十七页。void comb(int a,int m,int k) int i; for (i=m;i=k;i-) ak-1=i;if (k1) comb(a,i-1,k-1);else print(a); 第三十七页，共

32、五十七页。void main() int aMaxSize; printf(输入输入(shr)m,k(k=m):); scanf(%d%d,&m,&k); printf(1.%d中中%d个的组合结果如下个的组合结果如下:n,m,k); comb(a,m,k); printf(n);输入输入m,k(knqueen(k,n) 对于第对于第k行的每个合适的位置行的每个合适的位置i, 在其上放置一个皇后在其上放置一个皇后; 其他情况其他情况 queen(k+1,n); 设设queen(k+1,n)是是“小问题小问题”，queen(k,n)是是“大问题大问题”，则求，则求解皇后解皇后(hunghu)问题

33、的递归模型如下：问题的递归模型如下：第四十页，共五十七页。得到得到(d do)递归过程如下：递归过程如下：void queen(int k,int n) if (kn)输出一个解输出一个解; elsefor (j=1;j=n;j+)/在第在第k行找所有的列位置行找所有的列位置 if (第第k行的第行的第j列合适列合适) 在在(k,j)位置处放一个皇后即位置处放一个皇后即qk=jqueen(k+1,n); 第四十一页，共五十七页。int qN;/存放各皇后存放各皇后(hunghu)所在的所在的列号列号 对于对于(duy)(k,j)位置上的皇后，是否与已放好的皇后位置上的皇后，是否与已放好的皇后(

34、i,qi)（1ik- -1）有冲突呢？）有冲突呢？ 只要只要(zhyo)满足以下条件，则存在冲突，否则不冲突：满足以下条件，则存在冲突，否则不冲突：(qi=j) | (abs(qi- -j)=abs(k- -i)第四十二页，共五十七页。int place(int k,int j) /测试测试(k,j)位置能否摆放皇后位置能否摆放皇后(hunghu) int i=1; while (in) print(n); /所有皇后放置结束所有皇后放置结束(jish) elsefor (j=1;j0) /栈不空时循环栈不空时循环 i=st.top;/当前皇后为第当前皇后为第i个皇后个皇后 if (st.to

35、p=n)/所有皇后均放好所有皇后均放好,输出一个解输出一个解 printf( 第第%d个解：个解：,+count); for (k=1;k=st.top;k+) printf(%d,%d) ,k,st.colk); printf(n); 第四十五页，共五十七页。find=false;for (j=1;j0) if (st.colst.top=n) /本行没有可放位置本行没有可放位置,退栈退栈 st.top-; for (j=st.colst.top+1;jn)/当前皇后在本行没有可放的位置当前皇后在本行没有可放的位置st.top-;/退栈退栈 else /本行找到一个位置后退出回溯本行找到一个

36、位置后退出回溯break; 第四十七页，共五十七页。递归程序递归程序(chngx)1的执行：的执行：#include void fun(int i)if (i=1) printf(1:%dn,i);fun(i-1);printf(2:%dn,i); void main() fun(5);第四十八页，共五十七页。fun(5)输出输出1:5fun(4)输出输出(shch)2:5输出输出(shch)1:4fun(3)输出输出(shch)2:4输出输出1:3fun(2)输出输出2:3输出输出1:2fun(1)输出输出2:2输出输出1:1fun(0)输出输出2:11:51:41:31:21:12:12:

37、22:32:42:5执行结果：执行结果：函数参数构成状态，参数的变化就是状态的变化。函数参数构成状态，参数的变化就是状态的变化。第四十九页，共五十七页。递归程序递归程序(chngx)2的执行：的执行：#include int m;void fun(int i) if (i=1) printf(1:i=%d,m=%dn,i,m); m+; fun(i-1); printf(2:i=%d,m=%dn,i,m); void main() m=5; fun(5);第五十页，共五十七页。fun(5)输出输出(shch)1:i=5,m=5fun(4)输出输出(shch)2:i=5,m=10输出输出(shc

38、h)1:i=4,m=6fun(3)输出输出2:i=4,m=10输出输出1:i=3,m=7fun(2)输出输出2:i=3,m=10输出输出1:i=2,m=8fun(1)输出输出2:i=2,m=10输出输出1:i=1,m=9fun(0)输出输出2:i=1,m=101:i=5,m=51:i=4,m=61:i=3,m=71:i=2,m=81:i=1,m=92:i=1,m=102:i=2,m=102:i=3,m=102:i=4,m=102:i=5,m=10执行结果：执行结果：全局变量不会自动恢复。全局变量不会自动恢复。第五十一页，共五十七页。 例如，采用例如，采用(ciyng)递归算法求解迷宫问题，并输

39、出从入口到出递归算法求解迷宫问题，并输出从入口到出口的所有迷宫路径。口的所有迷宫路径。 设设mgpath(int xi,int yi,int xe,int ye,PathType path)是求从是求从(xi,yi)到到(xe,ye)的迷宫路径，用的迷宫路径，用path变量保存迷宫路径，其中变量保存迷宫路径，其中PathType类型定义如下：类型定义如下：typedef struct int i;/当前当前(dngqin)方块的行号方块的行号 int j;/当前方块的列号当前方块的列号 Box;typedef struct Box dataMaxSize; int length;/路径长度路径

40、长度 PathType;/定义路径类型定义路径类型第五十二页，共五十七页。求解迷宫问题求解迷宫问题(wnt)的递归模型如下：的递归模型如下：(xi,yi)(i,j)(xe,ye)mgpath(xi,yi,xe,ye,path)mgpath(i,j,xe,ye,path)mgpath(xi,yi,xe,ye,path)将将(xi,yi)添加到添加到path中中; 输出输出path中的迷宫路径中的迷宫路径; 若若(xi,yi)=(xe,ye)mgpath(xi,yi,xe,ye,path)将将(xi,yi)添加到添加到path中中; 找出找出(xi,yi)四周的一个相邻方块四周的一个相邻方块(fn

41、 kui)(i,j); mgxiyi=-1; mgpath(i,j,xe,ye,path); path回退一步并置回退一步并置mgxiyi=0; 若若(xi,yi)不为出口且可走不为出口且可走第五十三页，共五十七页。void mgpath(int xi,int yi,int xe,int ye,PathType path)/求解路径为求解路径为:(xi,yi)-(xe,ye) int di,k,i,j; if (xi=xe & yi=ye)/找到了出口找到了出口,输出路径输出路径 path.datapath.length.i = xi;path.datapath.length.j = yi;p

42、ath.length+;printf(迷宫路径迷宫路径%d如下如下:n,+count);for (k=0;kpath.length;k+) printf(t(%d,%d),path.datak. i,path.datak.j); if (k+1)%5=0)/每输出每每输出每5个方块个方块(fn kui)后换一行后换一行 printf(n);printf(n); 第五十四页，共五十七页。 else/(xi,yi)不是出口不是出口 if (mgxiyi=0)/(xi,yi)是一个可走方块是一个可走方块(fn kui) di=0; while (didata)。（7）输出以L为首节点指针的单链表中最小节点值。位置1和位置0的求法类似，属“小问题”。设计一个程序(chngx)求解组合问题：从自然数1n中任取r个数的所有组合。if (第k行的第j列合适)。printf(1:%dn,i)。printf(2:%dn,i)。通过学习递归算法设计有什么收获第五十七页，共五十七页。