遞歸的概念遞歸過程與遞歸工作棧遞歸與回溯廣義表,第五章遞歸與廣義表,遞歸的概念,遞歸的定義若一個(gè)對(duì)象部分地包含它自己,或用它自己給自己定義,則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過程直接地或間接地調(diào)用自己,則稱這個(gè)過程是遞歸的過程。以下三種情況常常用到遞歸方法。定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問題的解法是遞歸的,定義是遞歸的,求解階乘函數(shù)的遞歸算法longFactorial(longn)if(n=0)return1;elsereturnn*Factorial(n-1);,例如，階乘函數(shù),求解階乘n!的過程,主程序main:fact(4),參數(shù)4計(jì)算4*fact(3)返回24,參數(shù)3計(jì)算3*fact(2)返回6,參數(shù)2計(jì)算2*fact(1)返回2,參數(shù)1計(jì)算1*fact(0)返回1,參數(shù)0直接定值=1返回1,參數(shù)傳遞,結(jié)果返回,遞歸調(diào)用,回歸求值,數(shù)據(jù)結(jié)構(gòu)是遞歸的,一個(gè)結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個(gè)單鏈表;一個(gè)結(jié)點(diǎn)，它的指針域指向單鏈表，仍是一個(gè)單鏈表。,例如，單鏈表結(jié)構(gòu),f,f,搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值templatevoidPrint(ListNode*f)if(f-link=NULL)coutdatalink);,f,f,f,f,f,a0,a1,a2,a3,a4,遞歸找鏈尾,在鏈表中尋找等于給定值的結(jié)點(diǎn)并打印其數(shù)值templatevoidPrint(ListNode*f,Type,f,f,f,f,遞歸找含x值的結(jié)點(diǎn),x,問題的解法是遞歸的例如，漢諾塔(TowerofHanoi)問題的解法：如果n=1，則將這一個(gè)盤子直接從A柱移到C柱上。否則，執(zhí)行以下三步：用C柱做過渡，將A柱上的(n-1)個(gè)盤子移到B柱上：將A柱上最后一個(gè)盤子直接移到C柱上；用A柱做過渡，將B柱上的(n-1)個(gè)盤子移到C柱上。,#include#includestrclass.h”voidHanoi(intn,StringA,StringB,StringC)/解決漢諾塔問題的算法if(n=1)coutmoveAtoCendl;elseHanoi(n-1,A,C,B);coutmoveAtoCn=n;w-tag=1;S.push(w);n-;/向左遞歸到底,邊走邊進(jìn)棧sum=sum+n;/執(zhí)行求和,while(!S.IsEmpty()w=S.getTop();S.Pop();if(w-tag=1)/改為向右遞歸w-tag=2;S.push(w);n=w-n2;/F(n)右側(cè)為F(n-2)break;while(!S.IsEmpty();returnsum;,單向遞歸用迭代法實(shí)現(xiàn),longFibIter(longn)if(n=1)returnn;longtwoback=0,oneback=1,Current;for(inti=2;i=0)coutAn=0)coutvalueAnendl;n-;,遞歸與回溯常用于搜索過程,n皇后問題在n行n列的國(guó)際象棋棋盤上，若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線上，則稱為它們?yōu)榛ハ喙?。n皇后問題是指找到這n個(gè)皇后的互不攻擊的布局。,1#主對(duì)角線3#主對(duì)角線5#主對(duì)角線,0#次對(duì)角線2#次對(duì)角線4#次對(duì)角線6#次對(duì)角線,1#次對(duì)角線3#次對(duì)角線5#次對(duì)角線,0#主對(duì)角線2#主對(duì)角線4#主對(duì)角線6#主對(duì)角線,0123,0123,k=i+j,k=n+i-j-1,解題思路,安放第i行皇后時(shí)，需要在列的方向從0到n-1試探(j=0,n-1)在第j列安放一個(gè)皇后：如果在列、主對(duì)角線、次對(duì)角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第j列安放的皇后。如果沒有出現(xiàn)攻擊，在第j列安放的皇后不動(dòng)，遞歸安放第i+1行皇后。,設(shè)置4個(gè)數(shù)組coln：coli標(biāo)識(shí)第i列是否安放了皇后md2n-1:mdk標(biāo)識(shí)第k條主對(duì)角線是否安放了皇后sd2n-1:sdk標(biāo)識(shí)第k條次對(duì)角線是否安放了皇后qn:qi記錄第i行皇后在第幾列,voidQueen(inti)for(intj=0;jn;j+)if(第i行第j列沒有攻擊)在第i行第j列安放皇后；if(i=n-1)輸出一個(gè)布局；elseQueen(i+1);撤消第i行第j列的皇后；,算法求精voidQueen(inti)for(intj=0;jn;j+)if(!colj/*在第i行第j列安放皇后*/,if(i=n-1)/*輸出一個(gè)布局*/for(j=0;jn;j+)coutqj,;couttlink=NULL)returnNULL;elsereturnfirst-tlink;GenListNode*GenList:Next(GenListNode*elem)if(elem-tlink=NULL)returnNULL;elsereturnelem-tlink;,廣義表的遞歸算法,廣義表的復(fù)制算法voidGenList:Copy(constGenList,switch(ls-utype)case0:q-value.ref=ls-value.ref;break;case1:grinfo=grinfo;break;case2:q-value.charinfo=ls-value.charinfo;break;case3:q-value.hlink=Copy(ls-value.hlink);,q-tlink=Copy(ls-tlink);returnq;,求廣義表的深度,例如，對(duì)于廣義表E(B(a,b),D(B(a,b),C(u,(x,y,z),A(),1,1,1,1,2,3,4,intGenList:depth(GenListNode*ls)if(ls-tlink=NULL)return1;/空表GenListNode*temp=ls-tlink;intm=0;while(temp!=NULL)/在表頂層橫掃if(temp-utype=3)/結(jié)點(diǎn)為表結(jié)點(diǎn)intn=depth(temp-value.hlink);if(mtlink;returnm+1;,intGenList:depth()returndepth(first);,廣義表的刪除算法,01,15,3,3,12,01,2x,01,01,2y,ls,3,2x,掃描子鏈表若結(jié)點(diǎn)數(shù)據(jù)為x,刪除?？赡茏鲅h(huán)連續(xù)刪。若結(jié)點(diǎn)數(shù)據(jù)不為x，不執(zhí)行刪除。若結(jié)點(diǎn)為子表，遞歸在子表執(zhí)行刪除。,掃描子鏈表若結(jié)點(diǎn)數(shù)據(jù)為x,刪除。可能做循環(huán)連續(xù)刪。若結(jié)點(diǎn)數(shù)據(jù)不為x，不執(zhí)行刪除。若結(jié)點(diǎn)為子表，遞歸在子表執(zhí)行刪除。,voiddelvalue(GenListNode*ls,constvaluex)/在廣義表中刪除所有含x的結(jié)點(diǎn)if(ls-tlink!=NULL)/非空表GenListNode*p=ls-tlink;,wh