数据结构6递归

复习一、常见特殊矩阵的存储规律：对称矩阵、上(下)三角矩阵、对角矩阵、三对角矩阵二、稀疏矩阵的处理•存储结构：-非零元的表示：三元信息组(r,c,d)-行逻辑连接的顺序表表示-十字链表•应用：矩阵的转置(两种算法)、矩阵相乘、一元或多元多项式运算第六章递归递归是解决计算机和数学问题的一个有效工具，同时也是一种化繁为简的思维方式。在程序设计语言中可以用它来定义语言的语法，在数据结构中可以用它来编制表和树结构的查找和排序算法。递归也应用在组合数学领域用来处理计数和可能性问题。无论在理论还是在实际应用方面，递归都是算法研究、博弈论和图论的重要课题。在软件设计中递归是一个重要的算法设计方法和技术，递归子程序是通过调用自身来完成与自身要求相同的子问题的求解，并利用系统内部功能自动实现调用过程中信息的保存与恢复，因而省略了程序设计中的许多细节操作，简化了程序设计过程，使程序设计人员可以集中注意力于主要问题的求解上。6.1什么是递归6.1.1递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。递归就是一个事件或对象部分由自己组成，或者按它自己定义。一般程序调用：主程序┇调用子程序A┇return子程序A┇调用子程序B┇return子程序B┇┇┇return递归程序调用：程序proc┇┇调用程序proc┇return递归程序也必须有出口，其过程比较繁琐。递归问题举例：例6.1定义一个人的后代概念如下：⑴这个人的子女是它的后代；⑵这个人的子女的后代也是他的后代。即定义后代概念时有使用了这个概念。一、递归算法的组成函数或过程直接或间接调用自己的算法称为递归算法。递归算法包括：⑴递推：就是为得到问题的解，将其推倒比原来问题简单的问题的求解。使用递推时应注意到，递推应有终止之时。如求n!：阶乘Fact(n)=1,n=0n*Fact(n-1),n0这里的n=0，即0!=1为递推的终止条件。⑵回归：就是指当“简单问题得到解后，回归到原问题的解上”。如在求n!时，当计算完(n-1)!后，回归到计算n(n-1)上。但是在使用回归时应注意，递归算法所涉及的参数与局部变量是有层次的。回归并不引起其他动作。二、递归方法分类递归过程又称为自调用过程。递归过程是利用栈的技术来实现的。只不过这个过程是系统自动完成的。常见的递归方法有：⑴直接递归：就是函数或过程直接调用本身。如(a)所示。A(){┇callA()┇}图(a)⑵间接递归：一个函数或过程如果在调用其他函数或过程时，又产生了对自身的调用。如(b)图所示。A(){┇callB()┇}B(){┇callA()┇}图(b)⑶尾递归：在一个递归过程或递归函数中递归调用语句是最后一条执行语句。例6.2以下是求n!(n为正整数)的递归函数。intfun(intn){intx;if(n==1)/*语句1*/x=1;/*语句2*/else/*语句3*/x=fun(n-1)*n;/*语句4*/return(x);/*语句5*/}在该函数fun(n)求解过程中，直接调用fun(n-1)(语句4)自身，所以它是一个直接递归函数。又由于递归调用是最后一条执行语句，所以它又属于尾递归。6.1.2递归调用的实现原理-栈与递归的实现(教材的6.2)一、函数调用时的现场处理原则1.每调用一个函数，要将当前“现场信息”即当前参数、返回地址等压入栈顶，2.每当从一个函数退出时要将栈顶保存的最近一次的函数调用信息弹出即“恢复现场”，3.返回调用函数时,当前存储区保存的是调用时的现场内容。二、现场处理的基本方法1.系统建立一个“递归工作栈”,作为整个递归函数运行期间使用的数据存储区;2.每进行一次调用便生成一个“工作记录”，其内容如下:所有需要传递的参数、所有局部变量、返回地址并压入栈顶;3.退出一次递归时从栈顶弹出一个工作记录，按栈顶元素记录的返回地址继续执行;即利用栈实现现场保护与现场恢复。如例6.2求n!(n为正整数)递归函数执行过程中栈的变化记录：intfun(intn){intx;if(n==1)/*语句1*/x=1;/*语句2*/else/*语句3*/x=fun(n-1)*n;/*语句4*/return(x);/*语句5*/}栈中元素即现场保护工作记录的结构:(返回地址语句号,传来的n)假设n=5，返回地址为0表示程序结束。执行顺序现场记录栈中元素开始执行调用fun(0,5)1,3,4产生递归(d4,4)结束时返回fun(4)值*5(执行语句4)(0,5)(d4,4)1,3,4(d4,3)结束时返回fun(3)值*4(执行语句4)(0,5)(d4,4)(d4,3)1,3,4(d4,2)结束时返回fun(2)值*3(执行语句4)(0,5)(d4,4)(d4,3)(d4,2)1,3,4(d4,1)结束时返回fun(1)值*2(执行语句4)(0,5)(d4,4)(d4,3)(d4,2)(d4,1)结束递归1,2,5求得f(1)=1栈顶元素出栈恢复现场，并按记录执行语句44-5递归结束已知f(1)=1求得f(2)=f(1)*2弹出栈顶元素，即执行语句4intfun(intn){intx;if(n==1)/*语句1*/x=1;/*语句2*/else/*语句3*/x=fun(n-1)*n;/*语句4*/return(x);/*语句5*/}栈中元素即现场保护工作记录的结构:(返回地址语句号,传来的n)假设n=5，返回地址为0表示程序结束。1,3,4(d4,2)结束时返回fun(2)值*3(执行语句4)(0,5)(d4,4)(d4,3)(d4,2)1,3,4(d4,1)结束时返回fun(1)值*2(执行语句4)(0,5)(d4,4)(d4,3)(d4,2)(d4,1)1,2,5求得f(1)=1栈顶元素出栈恢复现场，并按记录执行语句44-5递归结束已知f(1)=1求得f(2)=f(1)*2弹出栈顶元素，即执行语句44-5递归结束已知f(2)=2求得f(3)=2*3弹出栈顶元素4-5递归结束已知f(3)=6求得f(4)=6*4弹出栈顶元素4-5递归结束已知(4)=24求得f(5)=24*5并执行语句0分析下面程序：dunno(intm)1{2intvalue;3if(m==0)4value=3;5else6value=dunno(m–1)+5;7return(value);8}9执行语句n=dunno(3),则n的值是多少？执行的语句序列是什么？语句序列:m=31–4，6，7，第一次递归，递归前m=3即执行n=dunno(2)m=2m=21–4，6，7，第二次递归，递归前m=2即执行n=dunno(1)m=1m=11–4，6，7，第三次递归，递归前m=1即执行n=dunno(0)m=0m=01–5，m=08-9:结束第三次递归，返回3执行语句7:3+5后再执行8,9结束第二次递归执行语句7:8+5后再执行8,9结束第一次递归执行语句7:13+5后再执行8,9结束外界调用对应的非递归程序：intdunno(intm){intv=3,i;for(i=1;i=m;i++)v=v+5;return(v);}/*非递归方式求解*/Hanoi算法:voidmove(intn,chara,charb,charc)1{2if(n==1)3movedisk(1,a,c);4else{5move(n-1,a,c,b);6movedisk(n,a,c);7move(n-1,b,a,c);8}9}movedisk函数:voidmovedisk(inti,chara,charc){printf(“\n%d;%c-%c”),i,a,c);}栈中元素即现场保护工作记录的结构:(返回地址,圆盘个数n,原在柱名a,临时柱名b,移到柱名c)返回地址以语句编号表示,塔的初始形式:3211{2if(n==1)3movedisk(1,a,c);4else{5move(n-1,a,c,b);6movedisk(n,a,c);7move(n-1,b,a,c);8}9}语句行号递归栈工作状态(已保存的记录)返回语句,盘数,原柱a,临时柱b,目的柱c说明塔的形状主函数调用时产生现场(0,3,a,b,c)进栈,0为主函调用后返回语句行号0,3,a,b,c原状1245当前现场(0,3,a,b,c)此次调用传来的参数下一现场由move(n-1,a,c,b)产生为:传来(第1参,第2参,第3参,第4参,第5参)生成现场用(第2参-1,第3参,第5参,第4参)(6,2,a,c,b)0,3,a,b,c6,2,a,c,b原状n=21245当前现场(6,2,a,c,b)即传来的参数现场准备(6,n-1,a,c,b)=(6,1,a,b,c)现场(6,1,a,b,c)进栈0,3,a,b,c6,2,a,c,b6,1,a,b,c原状n=11239当前现场(6,1,a,b,c)即传来的参数执行3:movedisk(1,a,c)=即1从a-c213执行9:按栈顶指示转向行号6,并弹出栈顶记录恢复现场(6,2,a,c,b)0,3,a,b,c6,2,a,c,b6,1,a,b,c1{2if(n==1)3movedisk(1,a,c);4else{5move(n-1,a,c,b);6movedisk(n,a,c);7move(n-1,b,a,c);8}9}67当前现场(6,2,a,c,b)即传来的参数执行6:movedisk(n,a,c)=即2从a-b321执行7:现场准备(n-1,b,a,c)=(1,c,a,b)现场(8,1,c,a,b)进栈0,3,a,b,c6,2,a,c,b6,7当前现场(6,2,a,c,b)执行6:movedisk(n,a,c)=即2从a-b执行7:现场准备(n-1,b,a,c)=(1,c,a,b)现场(8,1,c,a,b)进栈3210,3,a,b,c6,2,a,c,b8,1,c,a,b1{2if(n==1)3movedisk(1,a,c);4else{5move(n-1,a,c,b);6movedisk(n,a,c);7move(n-1,b,a,c);8}9}1,2,3,9当前现场(8,1,c,a,b)执行3:movedisk(1,a,c)=即1从c-b321执行9:按栈顶指示转向行号8,并弹出栈顶记录恢复现场(6,2,a,c,b)0,3,a,b,c6,2,a,c,b8,9当前现场(6,2,a,c,b)执行9:按栈顶指示转向行号6,并弹出栈顶记录恢复现场(0,3,a,b,c)0,3,a,b,c不变1{2if(n==1)3movedisk(1,a,c);4else{5move(n-1,a,c,b);6movedisk(n,a,c);7move(n-1,b,a,c);8}9}6,7当前现场(0,3,a,b,c)执行6:movedisk(n,a,c)=即3从a-c213执行7:现场准备(n-1,b,a,c)=(2,b,a,c)现场(8,2,b,a,c)进栈0,3,a,b,c8,2,b,a,c1,2,4,5当前现场(8,2,b,a,c)现场准备(n-1,a,c,b)=(1,b,c,a)现场(6,1,b,c,a)进栈不变1,2,4,50,3,a,b,c8,2,b,a,c当前现场(8,2,b,a,c)现场准备(n-1,a,c,b)=(1,b,c,a)现场(6,1,b,c,a)进栈2130,3,a,b,c8,2,b,a,c6,1,b,c,a1{2if(n==1)3movedisk(1,a,c);4else{5move(n-1,a,c,b);6movedisk(n,a,c);7move(n-1,b,a,c);8}9}1,2,3,9当前现场(6,1,b,c,a)执行3:movedisk(1,a,c)=即1从b-a321执行9:按栈顶指示转向行号6,并弹出栈顶记录恢复现场(8,2,b,a,c)0,3,a,b,c8,2,b,a,c6,7当前现场(8,2,b,a,c)执行6:movedisk(n,a,c)=即2从b-c321执行7:现场准备(n-1,b,a