数据结构05

1递归的概念递归过程与递归工作栈递归与回溯广义表2递归的概念递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。以下三种情况常常用到递归方法。定义是递归的数据结构是递归的问题的解法是递归的3定义是递归的求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如，阶乘函数时当时当1,)!1(0,1!nnnnn4求解阶乘n!的过程主程序main:fact(4)参数4计算4*fact(3)返回24参数3计算3*fact(2)返回6参数2计算2*fact(1)返回2参数1计算1*fact(0)返回1参数0直接定值=1返回1参数传递结果返回递归调用回归求值5一个结点，它的指针域为NULL，是一个单链表;一个结点，它的指针域指向单链表，仍是一个单链表。例如，单链表结构ff数据结构是递归的6搜索链表最后一个结点并打印其数值templateclassTXvoidPrint(ListNodeTX*f){if(f-link==NULL)coutf-dataendl;elsePrint(f-link);}fffffa0a1a2a3a4递归找链尾7ffff递归找含x值的结点x在链表中寻找等于给定值的结点并打印其数值templateclassTXvoidPrint(ListNodeTX*f,TX&x){if(f!=NULL)if(f-data==x)coutf-dataendl;elsePrint(f-link,x);}8例如，汉诺塔(TowerofHanoi)问题问题的解法是递归的解法：如果n=1，则将这一个盘子直接从A柱移到C柱上。否则，执行以下三步：①用C柱做过渡，将A柱上的(n-1)个盘子移到B柱上；②将A柱上最后一个盘子直接移到C柱上；③用A柱做过渡，将B柱上的(n-1)个盘子移到C柱上。910#includeiostream.hvoidHanoi(intn,charL,charM,charR){//解决汉诺塔问题的算法if(n==1)coutmoveLtoRendl;else{Hanoi(n-1,L,R,M);coutmoveLtoRendl;Hanoi(n-1,M,L,R);}}11递归思想1、分治法：分解-求解的策略复杂问题分解为相对简单且解法相同或类似的子问题，解决这些子问题，原问题即获解决2、递归结束条件：子问题可以直接解决12迷宫问题小型迷宫路口动作结果1(入口)正向走进到22左拐弯进到33右拐弯进到44(堵死)回溯退到33(堵死)回溯退到22正向走进到55(堵死)回溯退到22右拐弯进到66左拐弯进到7(出口)43521766左0直2右0行3行5行60040000007007小型迷宫的数据13迷宫的类定义#includeiostream.h#includefstream.h#includestdlib.hclassMaze{private:intMazeSize;intEXIT;Intersection*intsec;public:Maze(char*filename);intTraverseMaze(intCurrentPos);};交通路口结构定义structIntersection{intleft;intforward;intright;}14Maze::Maze(char*filename){//从文件filename中读取各路口和出口的数据ifstreamfin;fin.open(filename,ios::in|ios::nocreate);if(!fin){cout“文件”filename“打不开”endl;exit(1);}finMazeSize;//输入迷宫路口数intsec=newIntersection[MazeSize+1];//创建迷宫路口数组for(inti=1;i=MazeSize;i++)finintsec[i].leftintsec[i].forwardintsec[i].right;finEXIT;//输入迷宫出口fin.close();}15迷宫漫游与求解算法intMaze::TraverseMaze(intCurrentPos){if(CurrentPos0){//路口从1开始if(CurrentPos==EXIT)//出口处理{coutCurrentPos;return1;}else//递归向左搜寻可行途径if(TraverseMaze(intsec[CurrentPos].left)){coutCurrentPos“”;return1;}else//递归向前搜寻可行途径if(TraverseMaze(intsec[CurrentPos].forward)){coutCurrentPos“”;return1;}else//递归向右搜寻可行途径if(TraverseMaze(intsec[CurrentPos].right)){coutCurrentPos;return1;}}return0;}16递归过程与递归工作栈递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反：递归调用n!(n-1)!(n-2)!1!0!=1返回次序主程序第一次调用递归过程为外部调用；递归过程每次递归调用自己为内部调用。它们返回调用它的过程的地址不同。17递归工作栈每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。局部变量返回地址参数活动记录框架递归工作记录18函数递归时的活动记录y=fx(…);下一条指令intfx(参数表){……………….returnx;}调用块函数块返回地址(下一条指令)局部变量参数19longFactorial(longn){inttemp;if(n==0)return1;elsetemp=n*Factorial(n-1);RetLoc2returntemp;}voidmain(){intn;n=Factorial(4);RetLoc1}20计算Fact时活动记录的内容递归调用序列0RetLoc21RetLoc22RetLoc23RetLoc24RetLoc1参数返回地址返回时的指令RetLoc1return4*6//返回24RetLoc2return3*2//返回6RetLoc2return1//返回1RetLoc2return1*1//返回1RetLoc2return2*1//返回221递归过程改为非递归过程递归过程简洁、易编、易懂递归过程效率低，重复计算多改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程22计算斐波那契数列的函数Fib(n)的定义求解斐波那契数列的递归算法longFib(longn){if(n=1)returnn;elsereturnFib(n-1)+Fib(n-2);}1n2),Fib(n1)Fib(n0,1nn,)Fib(n如F0=0,F1=1,F2=1,F3=2,F4=3,F5=523调用次数NumCall(k)=2*Fib(k+1)-1。斐波那契数列的递归调用树Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)24Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)栈结点ntagtag=1,向左递归；tag=2,向右递归25Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)213141n=1sum=0+1223141n=2-23141n=0sum=1+03241n=3-241n=1sum=1+142n=4-226Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2142n=1sum=2+12242n=2-242n=0sum=3+027longFibnacci(longn){StackNodeS;Node*w;longsum=0;//反复执行直到所有终端结点数据累加完do{while(n1){w-n=n;w-tag=1;S.push(w);n--;}//向左递归到底,边走边进栈sum=sum+n;//执行求和28while(!S.IsEmpty()){w=S.getTop();S.Pop();if(w-tag==1){//改为向右递归w-tag=2;S.push(w);n=w-n–2;//F(n)右侧为F(n-2)break;}}}while(!S.IsEmpty());returnsum;}29单向递归用迭代法实现longFibIter(longn){if(n=1)returnn;longtwoback=0,oneback=1,Current;for(inti=2;i=n;i++){Current=twoback+oneback;twoback=oneback;oneback=Current;}returnCurrent;}30voidrecfunc(intA[],intn){if(n=0){coutA[n]“”;n--;recfunc(A,n);}}2536721899495463尾递归用迭代法实现31voidsterfunc(intA[],intn){//消除了尾递归的非递归函数while(n=0){coutvalueA[n]endl;n--;}}32递归与回溯常用于搜索过程n皇后问题在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指找到这n个皇后的互不攻击的布局。331#主对角线3#主对角线5#主对角线0#次对角线2#次对角线4#次对角线6#次对角线1#次对角线3#次对角线5#次对角线0#主对角线2#主对角线4#主对角线6#主对角线01230123k=i+jk=n+i-j-134皇后问题解题思路安放第i行皇后时，需要在列的方向从0到n-1试探(j=0,…,n-1)在第j列安放一个皇后：如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第j列安放的皇后。如果没有出现攻击，在第j列安放的皇后不动，递归安放第i+1行皇后。35设置4个数组col[n]：col[j]标识第j列是否安放了皇后md[2n-1]:md[k]标识第k条主对角线是否安放了皇后sd[2n-1]:sd[k]标识第k条次对角线是否安放了皇后q[n]:q[i]记录第i行皇后在第几列36voidQueen(inti){for(intj=0;jn;j++){if(第i行第j列没有攻击){在第i行第j列安放皇后；if(i==n-1)输出一个布局；elseQueen(i+1);撤消第i行第j列的皇后；}}}37皇后算法求精voidQueen(inti){for(intj=0;jn;j++){if(!col[j]&&!md[n+i-j-1]&&!sd[i+j]){//第i行第j列没有攻击现象q[i]=j;col[j]=md[n+i-j-1]=sd[i+j]=1;//在i行j列安放皇后并设置攻击数组if(i==n-1)Show();//输出一个布局