遞歸過(guò)程與遞歸工作棧課件

遞歸的概念遞歸過(guò)程與遞歸工作棧遞歸與回溯廣義表第五章遞歸與廣義表遞歸的概念第五章遞歸與廣義表遞歸的概念遞歸的定義若一個(gè)對(duì)象部分地包含它自己,或用它自己給自己定義,則稱(chēng)這個(gè)對(duì)象是遞歸的；若一個(gè)過(guò)程直接地或間接地調(diào)用自己,則稱(chēng)這個(gè)過(guò)程是遞歸的過(guò)程。以下三種情況常常用到遞歸方法。

定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問(wèn)題的解法是遞歸的遞歸的概念遞歸的定義若一個(gè)對(duì)象部分地包含它自己,或用定義是遞歸的求解階乘函數(shù)的遞歸算法longFactorial(longn){if(n==0)return1;

elsereturnn*Factorial(n-1);}例如，階乘函數(shù)定義是遞歸的求解階乘函數(shù)的遞歸算法例如，階乘函數(shù)求解階乘n!的過(guò)程主程序

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)用回歸求值求解階乘n!的過(guò)程主程序main:fact(4)參數(shù)據(jù)結(jié)構(gòu)是遞歸的

一個(gè)結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個(gè)單鏈表;

一個(gè)結(jié)點(diǎn)，它的指針域指向單鏈表，仍是一個(gè)單鏈表。

例如，單鏈表結(jié)構(gòu)ff數(shù)據(jù)結(jié)構(gòu)是遞歸的一個(gè)結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個(gè)單鏈搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值template<classType>

voidPrint(ListNode<Type>*f){if(f->link==NULL)

cout<<f->data<<

endl;elsePrint(f->link);}fffffa0a1a2a3a4遞歸找鏈尾搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值fffffa0a在鏈表中尋找等于給定值的結(jié)點(diǎn)并打印其數(shù)值

template<classType>

voidPrint(ListNode<Type>*f,Type&

x){

if(f!=NULL)

if(f->data==x)

cout<<f->data<<endl;

elsePrint(f->link,x);

}ffff遞歸找含x值的結(jié)點(diǎn)x在鏈表中尋找等于給定值的結(jié)點(diǎn)并打印其數(shù)值

template

問(wèn)題的解法是遞歸的

例如，漢諾塔(TowerofHanoi)問(wèn)題的解法：

如果

n=1，則將這一個(gè)盤(pán)子直接從

A柱移到

C柱上。否則，執(zhí)行以下三步：

①用

C柱做過(guò)渡，將

A柱上的

(n-1)個(gè)盤(pán)子移到

B柱上：

②將

A柱上最后一個(gè)盤(pán)子直接移到

C柱上；③用

A柱做過(guò)渡，將

B柱上的

(n-1)個(gè)盤(pán)子移到

C柱上。問(wèn)題的解法是遞歸的遞歸過(guò)程與遞歸工作棧課件#include<iostream.h>#include"strclass.h”void

Hanoi(intn,StringA,StringB,StringC){

//解決漢諾塔問(wèn)題的算法

if(n==1)cout<<"move"<<A<<"to"<<C<<endl;

else{Hanoi(n-1,A,C,B);

cout<<"move"<<A<<"to"<<C<<endl; Hanoi(n-1,B,A,C);

}}#include<iostream.h>遞歸過(guò)程與遞歸工作棧遞歸過(guò)程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，退出時(shí)的次序正好相反：

遞歸調(diào)用

n!(n-1)!(n-2)!1!0!=1

返回次序主程序第一次調(diào)用遞歸過(guò)程為外部調(diào)用；遞歸過(guò)程每次遞歸調(diào)用自己為內(nèi)部調(diào)用。它們返回調(diào)用它的過(guò)程的地址不同。遞歸過(guò)程與遞歸工作棧遞歸過(guò)程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。遞歸工作棧每一次遞歸調(diào)用時(shí)，需要為過(guò)程中使用的參數(shù)、局部變量等另外分配存儲(chǔ)空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。

局部變量返回地址參數(shù)活動(dòng)記錄框架遞歸工作記錄遞歸工作棧每一次遞歸調(diào)用時(shí)，需要為過(guò)程中使用的參數(shù)、局部變量函數(shù)遞歸時(shí)的活動(dòng)記錄……………….<下一條指令>Function(<參數(shù)表>)……………….<return>調(diào)用塊函數(shù)塊返回地址(下一條指令)局部變量參數(shù)函數(shù)遞歸時(shí)的活動(dòng)記錄……………….Function(<參數(shù)表

longFactorial(longn){inttemp;if(n==0)return1;elsetemp=n*Factorial(n-1);

RetLoc2

returntemp; }

voidmain(){ intn;

n=Factorial(4);

RetLoc1

}longFactori計(jì)算Fact時(shí)活動(dòng)記錄的內(nèi)容遞歸調(diào)用序列0RetLoc21RetLoc22RetLoc23RetLoc24RetLoc1參數(shù)返回地址返回時(shí)的指令RetLoc1return4*6//返回24

RetLoc2return3*2//返回6

RetLoc2return1//返回1

RetLoc2return1*1//返回1

RetLoc2return2*1//返回2

計(jì)算Fact時(shí)活動(dòng)記錄的內(nèi)容遞歸調(diào)用序列0RetLo遞歸過(guò)程改為非遞歸過(guò)程遞歸過(guò)程簡(jiǎn)潔、易編、易懂遞歸過(guò)程效率低，重復(fù)計(jì)算多改為非遞歸過(guò)程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過(guò)程其他情形必須借助棧實(shí)現(xiàn)非遞歸過(guò)程遞歸過(guò)程改為非遞歸過(guò)程遞歸過(guò)程簡(jiǎn)潔、易編、易懂計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義

求解斐波那契數(shù)列的遞歸算法

longFib(longn){

if(n<=1)returnn;

elsereturnFib(n-1)+Fib(n-2);}

如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義

求解斐波那契數(shù)列的調(diào)用次數(shù)

NumCall(k)=2*Fib(k+1)-1。斐波那契數(shù)列的遞歸調(diào)用樹(shù)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)調(diào)用次數(shù)NumCall(k)=2*Fib(k+1)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)棧結(jié)點(diǎn)ntagtag=1,向左遞歸；tag=2,向右遞歸Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(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-241n=1sum=1+142n=4-2Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(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+0Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)longFibnacci(longn){ Stack<Node>S;Node*w;longsum=0;

//反復(fù)執(zhí)行直到所有終端結(jié)點(diǎn)數(shù)據(jù)累加完

do{

while(n>1){

w->n=n;w->tag=1;S.push(w);n--;}

//向左遞歸到底,邊走邊進(jìn)棧

sum=sum+n;

//執(zhí)行求和

longFibnacci(longn){

while(!S.IsEmpty()){ w=S.getTop();S.Pop();

if(w->tag==1){//改為向右遞歸

w->tag=2;S.push(w);n=w->n–2;

//F(n)右側(cè)為F(n-2)

break;} } }while(!S.IsEmpty()); returnsum;}while(!S.IsEmpty())單向遞歸用迭代法實(shí)現(xiàn)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;}單向遞歸用迭代法實(shí)現(xiàn)longFibIter(longvoidrecfunc(intA[],intn){if(n>=0){

cout<<A[n]<<“”;n--;recfunc(A,n);}}

2536721899495463

尾遞歸用迭代法實(shí)現(xiàn)voidrecfunc(intA[],intvoidsterfunc(intA[],intn){//消除了尾遞歸的非遞歸函數(shù)

while(n>=0){cout<<"value"<<A[n]<<endl;n--;

}}

voidsterfunc(intA[],int遞歸與回溯

常用于搜索過(guò)程n皇后問(wèn)題 在n行n列的國(guó)際象棋棋盤(pán)上，若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線(xiàn)上，則稱(chēng)為它們?yōu)榛ハ喙?。n皇后問(wèn)題是指找到這

n個(gè)皇后的互不攻擊的布局。遞歸與回溯常用于搜索過(guò)程n皇后問(wèn)題1#主對(duì)角線(xiàn)3#主對(duì)角線(xiàn)5#主對(duì)角線(xiàn)0#次對(duì)角線(xiàn)2#次對(duì)角線(xiàn)4#次對(duì)角線(xiàn)6#次對(duì)角線(xiàn)1#次對(duì)角線(xiàn)3#次對(duì)角線(xiàn)5#次對(duì)角線(xiàn)0#主對(duì)角線(xiàn)2#主對(duì)角線(xiàn)4#主對(duì)角線(xiàn)6#主對(duì)角線(xiàn)01230123k=i+jk=n+i-j-11#主對(duì)角線(xiàn)0#次對(duì)角線(xiàn)1#次對(duì)角線(xiàn)0#主對(duì)角線(xiàn)0解題思路安放第i行皇后時(shí)，需要在列的方向從0到n-1試探(j=0,…,n-1)在第

j列安放一個(gè)皇后：如果在列、主對(duì)角線(xiàn)、次對(duì)角線(xiàn)方向有其它皇后，則出現(xiàn)攻擊，撤消在第

j

列安放的皇后。如果沒(méi)有出現(xiàn)攻擊，在第

j

列安放的皇后不動(dòng)，遞歸安放第i+1行皇后。解題思路安放第i行皇后時(shí)，需要在列的方向從0到n-設(shè)置4個(gè)數(shù)組

col[n]

：col[i]標(biāo)識(shí)第i列是否安放了皇后

md[2n-1]:md[k]標(biāo)識(shí)第k條主對(duì)角線(xiàn)是否安放了皇后

sd[2n-1]:sd[k]標(biāo)識(shí)第k條次對(duì)角線(xiàn)是否安放了皇后

q[n]:q[i]記錄第i行皇后在第幾列設(shè)置4個(gè)數(shù)組voidQueen(inti){for(intj=0;j<n;j++){if(第i行第j列沒(méi)有攻擊

){

在第i行第j列安放皇后；

if(i==n-1)

輸出一個(gè)布局；

elseQueen(i+1

);}

撤消第i行第j列的皇后；

}}voidQueen(inti){算法求精voidQueen(inti){for(intj=0;j<n;j++){if(!col[j]&&!md[n+i-j-1]&&!sd[i+j]){

/*第i行第j列沒(méi)有攻擊*/

col[j]=md[n+i-j-1]=sd[i+j]=1;

q[i]=j;

/*在第i行第j列安放皇后*/

算法求精

if(i==n-1){/*輸出一個(gè)布局*/

for(j=0;j<n;j++)

cout<<q[j]<<‘,’;cout<<endl;}elseQueen(i+1

);}

col[j]=md[n+i-j-1]=sd[i+j]=0;

q[i]=0;/*撤消第i行第j列的皇后*/}}if(i==n-1){廣義表(GeneralLists)

廣義表的概念n(0)個(gè)表元素組成的有限序列，記作

LS=(a0,a1,a2,…,an-1)

LS是表名，ai是表元素，它可以是表(稱(chēng)為子表)，可以是數(shù)據(jù)元素(稱(chēng)為原子)。

n為表的長(zhǎng)度。n=0的廣義表為空表。

n>0時(shí)，表的第一個(gè)表元素稱(chēng)為廣義表的表頭(head)，除此之外，其它表元素組成的表稱(chēng)為廣義表的表尾(tail)。

廣義表(GeneralLists)廣義表的概念n廣義表的特性有次序性有長(zhǎng)度A=()B=(6,2)C=(‘a(chǎn)’,(5,3,‘x’))D=(B,C,A)E=(B,D)F=(4,F)有深度可共享可遞歸廣義表的特性有次序性A=()有深度可遞歸遞歸過(guò)程與遞歸工作棧課件廣義表的表示只包括整數(shù)和字符型數(shù)據(jù)的廣義表鏈表表示

表中套表情形下的廣義表鏈表表示5232436103914list25list11247‘a(chǎn)’‘s’廣義表的表示只包括整數(shù)和字符型數(shù)據(jù)的廣義表鏈表表示表中套表廣義表結(jié)點(diǎn)定義結(jié)點(diǎn)類(lèi)型utype=0,表頭；=1,整型原子；=2,字符型原子；=3,子表值value

utype=0時(shí),存放引用計(jì)數(shù)(ref)；utype=1時(shí),存放整數(shù)值(intinfo)；utype=2時(shí),存放字符型數(shù)據(jù)(charinfo)；utype=3時(shí),存放指向子表表頭的指針(hlink)尾指針tlink

utype=0時(shí),指向該表第一個(gè)結(jié)點(diǎn)；utype0時(shí),指向同一層下一個(gè)結(jié)點(diǎn)

utypevaluetlink

廣義表結(jié)點(diǎn)定義結(jié)點(diǎn)類(lèi)型utype=0,表頭；=1廣義表的存儲(chǔ)表示EBF011430133D0115132‘x’012‘a(chǎn)’3C013330116DBBCA1201A廣義表的存儲(chǔ)表示EBF011430133D0廣義表的類(lèi)定義classGenList;

//GenList類(lèi)的前視聲明classGenListNode{ //廣義表結(jié)點(diǎn)類(lèi)的前視聲明structItems{//僅有結(jié)點(diǎn)信息的項(xiàng)friendclassGenlistNode;friendclassGenlist;intutype; //＝0/1/2/3union{ //聯(lián)合

廣義表的類(lèi)定義classGenList; //GenLiintref;//utype=0,存放引用計(jì)數(shù)

intintinfo; //utype=1,存放整數(shù)值

charcharinfo;//utype=2,存放字符

GenListNode*hlink; //utype=3,存放指向子表的指針

}}

classGenListNode{ //廣義表結(jié)點(diǎn)類(lèi)定義friendclassGenlist;private:intutype; //＝0/1/2/3intref;//GenListNode*tlink; //下一結(jié)點(diǎn)指針

union{ //聯(lián)合

intref; //utype=0,存放引用計(jì)數(shù)

intintinfo; //utype=1,存放整數(shù)值

charcharinfo;//utype=2,存放字符

GenListNode*hlink; //utype=3,存放指向子表的指針

}value;public:GenListNode():utype(0),tlink(NULL),ref(0){}

//構(gòu)造函數(shù),建表頭結(jié)點(diǎn)GenListNode*tlink; //下一結(jié)GenListNode(intt,GenListNode*next=

NULL){}

//構(gòu)造函數(shù)：建表結(jié)點(diǎn)

Items&Info(GenListNode*elem); //返回表元素elem的值

intnodetype(GenListNode*elem)

{returnelem->utype;

}

//返回表元素elem的數(shù)據(jù)類(lèi)型

GenListNode&setInfo(Items&x);

//將表元素elem中的值修改為x};GenListNode(intt,GenLiclassGenList{

//廣義表類(lèi)定義

private:GenListNode*first;//廣義表頭指針

GenListNode*Copy(GenListNode*ls);

//復(fù)制一個(gè)ls指示的無(wú)共享非遞歸表

intdepth(GenListNode*ls); //計(jì)算由

ls

指示的非遞歸表的深度

intequal(GenListNode*s,GenListNode*t); //比較以s和t為表頭的兩個(gè)表是否相等

voidRemove(GenListNode*ls); //釋放以ls

為表頭結(jié)點(diǎn)的廣義表classGenList{ public:Genlist();

//構(gòu)造函數(shù)

~GenList(); //析構(gòu)函數(shù)

GenListNode&Head();//返回表頭元素

GenList&Tail(); //返回表尾

GenListNode*First(); //返回第一個(gè)元素

GenListNode*Next(GenListNode*elem); //返回表元素elem的直接后繼元素

voidsetNext(GenListNode*elem1,

GenListNode*elem2);

//將elem2插到表中元素elem1后

public:voidCopy(constGenList&l);

//廣義表的復(fù)制

intdepth(); //計(jì)算一個(gè)非遞歸表的深度

intCreatelist(GenListNode*ls,

char*s);

//從廣義表的字符串描述

s

出發(fā),//建立一個(gè)帶表頭結(jié)點(diǎn)的廣義表結(jié)構(gòu)}

voidCopy(constGenList廣義表的訪(fǎng)問(wèn)算法

廣義表結(jié)點(diǎn)類(lèi)的存取成員函數(shù)Items&GenListNode::Info(GenListNode*elem){//返回表元素elem的值

Items*pitem=newItems;pitem->utype=elem->utype;

pitem->value=elem->value;

return*pitem;}廣義表的訪(fǎng)問(wèn)算法廣義表結(jié)點(diǎn)類(lèi)的存取成員函數(shù)GenListNode&GenListNode::setInfo(Items&x){ //修改表元素的值為xutype=x->utype;

value=x->value;

}

廣義表類(lèi)的構(gòu)造和訪(fǎng)問(wèn)成員函數(shù)Genlist::GenList(){//構(gòu)造函數(shù)

GenListNode*first=newGenListNode();

first->utype=0;first->ref=1;

first->tlink=NULL;}GenListNode&GenListNode::Items&GenList::Head(){//若廣義表非空，則返回其第一個(gè)元素的值，//否則函數(shù)沒(méi)有定義。

if(first->tlink==NULL)returnNULL;

else{

//非空表

Items*temp=newItems;temp->utype=frist->tlink->utype;temp->value=frist->tlink->value;

return*temp;

//返回類(lèi)型及值

}}Items&GenList::Head(){GenList&GenList::Tail(){//若廣義表非空，則返回廣義表除第一個(gè)元//素外其它元素組成的表,否則函數(shù)沒(méi)有定義

if(frist->tlink==NULL)returnNULL;

else{ //非空表

GenList*temp;

temp->first=Copy(first);return*temp;

}

}

GenList&GenList::Tail(){GenListNode*GenList::First(){if(first->tlink==NULL)returnNULL;

elsereturnfirst->tlink;}GenListNode*GenList::Next(GenListNode*elem){if(elem->tlink==NULL)returnNULL;

elsereturnelem->tlink;}GenListNode*GenList::廣義表的遞歸算法

廣義表的復(fù)制算法

voidGenList::Copy(constGenList&ls){first=Copy(ls.first); //共有函數(shù)}GenListNode*GenList::Copy(GenListNode*ls){ //私有函數(shù)

GenListNode*q=NULL;

if(ls!=NULL){q=newGenListNode(ls->utype,NULL

);廣義表的遞歸算法廣義表的復(fù)制算switch(ls->utype){

case0:q->value.ref=ls->value.ref;

break;case1:

q->grinfo=ls->grinfo;break;

case2:

q->value.charinfo=ls->value.charinfo;break; case3:

q->value.hlink=Copy(ls->value.hlink);

}

switch(ls->utype){

q->tlink=Copy(ls->tlink);}

returnq;}q->tlink=Copy(ls->t求廣義表的深度例如，對(duì)于廣義表

E(B(a,b),D(B(a,b),C(u,(x,y,z)),A()))1111234求廣義表的深度例如，對(duì)于廣義表1111234intGenList::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(m<n)m=n;//m記最大深度

}temp=temp->tlink;

}returnm+1;}intGenList::depth(GenListintGenList::depth(){

returndepth(first

);}廣義表的刪除算法01153312012‘x’01012‘y’ls32‘x’

掃描子鏈表若結(jié)點(diǎn)數(shù)據(jù)為‘x’,刪除?？赡茏鲅h(huán)連續(xù)刪。若結(jié)點(diǎn)數(shù)據(jù)不為‘x’，不執(zhí)行刪除。若結(jié)點(diǎn)為子表，遞歸在子表執(zhí)行刪除。intGenList::depth(){

掃描子鏈表若結(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;掃描子鏈表voiddelvalue(GenListNod

while(p!=

NULL&&

//橫掃鏈表

((p->utype==1&&

p->info==x)||

(p->utype==2&&

p->value.charinfo==x)){

ls->tlink=p->tlink;

deletep;//刪除

p=ls->tlink;//指向同一層后繼結(jié)點(diǎn)

}if(p!=NULL){

if(p->utype==3)

//在子表中刪除

delvalue(p->value.hlink,x);

while(p!=NULL&&

delvalue(p,x);//在后續(xù)鏈表中刪除

}}}

GenList::~GenList(){

//析構(gòu)函數(shù)

Remove(first);}voidGenList::Remove(GenListNode*ls){//私有函數(shù)：釋放以

ls為表頭指針的廣義表

ls->value.ref

--; //引用計(jì)數(shù)減1delvalue(p,x);遞歸的概念遞歸過(guò)程與遞歸工作棧遞歸與回溯廣義表第五章遞歸與廣義表遞歸的概念第五章遞歸與廣義表遞歸的概念遞歸的定義若一個(gè)對(duì)象部分地包含它自己,或用它自己給自己定義,則稱(chēng)這個(gè)對(duì)象是遞歸的；若一個(gè)過(guò)程直接地或間接地調(diào)用自己,則稱(chēng)這個(gè)過(guò)程是遞歸的過(guò)程。以下三種情況常常用到遞歸方法。

定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問(wèn)題的解法是遞歸的遞歸的概念遞歸的定義若一個(gè)對(duì)象部分地包含它自己,或用定義是遞歸的求解階乘函數(shù)的遞歸算法longFactorial(longn){if(n==0)return1;

elsereturnn*Factorial(n-1);}例如，階乘函數(shù)定義是遞歸的求解階乘函數(shù)的遞歸算法例如，階乘函數(shù)求解階乘n!的過(guò)程主程序

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)用回歸求值求解階乘n!的過(guò)程主程序main:fact(4)參數(shù)據(jù)結(jié)構(gòu)是遞歸的

一個(gè)結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個(gè)單鏈表;

一個(gè)結(jié)點(diǎn)，它的指針域指向單鏈表，仍是一個(gè)單鏈表。

例如，單鏈表結(jié)構(gòu)ff數(shù)據(jù)結(jié)構(gòu)是遞歸的一個(gè)結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個(gè)單鏈搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值template<classType>

voidPrint(ListNode<Type>*f){if(f->link==NULL)

cout<<f->data<<

endl;elsePrint(f->link);}fffffa0a1a2a3a4遞歸找鏈尾搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值fffffa0a在鏈表中尋找等于給定值的結(jié)點(diǎn)并打印其數(shù)值

template<classType>

voidPrint(ListNode<Type>*f,Type&

x){

if(f!=NULL)

if(f->data==x)

cout<<f->data<<endl;

elsePrint(f->link,x);

}ffff遞歸找含x值的結(jié)點(diǎn)x在鏈表中尋找等于給定值的結(jié)點(diǎn)并打印其數(shù)值

template

問(wèn)題的解法是遞歸的

例如，漢諾塔(TowerofHanoi)問(wèn)題的解法：

如果

n=1，則將這一個(gè)盤(pán)子直接從

A柱移到

C柱上。否則，執(zhí)行以下三步：

①用

C柱做過(guò)渡，將

A柱上的

(n-1)個(gè)盤(pán)子移到

B柱上：

②將

A柱上最后一個(gè)盤(pán)子直接移到

C柱上；③用

A柱做過(guò)渡，將

B柱上的

(n-1)個(gè)盤(pán)子移到

C柱上。問(wèn)題的解法是遞歸的遞歸過(guò)程與遞歸工作棧課件#include<iostream.h>#include"strclass.h”void

Hanoi(intn,StringA,StringB,StringC){

//解決漢諾塔問(wèn)題的算法

if(n==1)cout<<"move"<<A<<"to"<<C<<endl;

else{Hanoi(n-1,A,C,B);

cout<<"move"<<A<<"to"<<C<<endl; Hanoi(n-1,B,A,C);

}}#include<iostream.h>遞歸過(guò)程與遞歸工作棧遞歸過(guò)程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，退出時(shí)的次序正好相反：

遞歸調(diào)用

n!(n-1)!(n-2)!1!0!=1

返回次序主程序第一次調(diào)用遞歸過(guò)程為外部調(diào)用；遞歸過(guò)程每次遞歸調(diào)用自己為內(nèi)部調(diào)用。它們返回調(diào)用它的過(guò)程的地址不同。遞歸過(guò)程與遞歸工作棧遞歸過(guò)程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。遞歸工作棧每一次遞歸調(diào)用時(shí)，需要為過(guò)程中使用的參數(shù)、局部變量等另外分配存儲(chǔ)空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。

局部變量返回地址參數(shù)活動(dòng)記錄框架遞歸工作記錄遞歸工作棧每一次遞歸調(diào)用時(shí)，需要為過(guò)程中使用的參數(shù)、局部變量函數(shù)遞歸時(shí)的活動(dòng)記錄……………….<下一條指令>Function(<參數(shù)表>)……………….<return>調(diào)用塊函數(shù)塊返回地址(下一條指令)局部變量參數(shù)函數(shù)遞歸時(shí)的活動(dòng)記錄……………….Function(<參數(shù)表

longFactorial(longn){inttemp;if(n==0)return1;elsetemp=n*Factorial(n-1);

RetLoc2

returntemp; }

voidmain(){ intn;

n=Factorial(4);

RetLoc1

}longFactori計(jì)算Fact時(shí)活動(dòng)記錄的內(nèi)容遞歸調(diào)用序列0RetLoc21RetLoc22RetLoc23RetLoc24RetLoc1參數(shù)返回地址返回時(shí)的指令RetLoc1return4*6//返回24

RetLoc2return3*2//返回6

RetLoc2return1//返回1

RetLoc2return1*1//返回1

RetLoc2return2*1//返回2

計(jì)算Fact時(shí)活動(dòng)記錄的內(nèi)容遞歸調(diào)用序列0RetLo遞歸過(guò)程改為非遞歸過(guò)程遞歸過(guò)程簡(jiǎn)潔、易編、易懂遞歸過(guò)程效率低，重復(fù)計(jì)算多改為非遞歸過(guò)程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過(guò)程其他情形必須借助棧實(shí)現(xiàn)非遞歸過(guò)程遞歸過(guò)程改為非遞歸過(guò)程遞歸過(guò)程簡(jiǎn)潔、易編、易懂計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義

求解斐波那契數(shù)列的遞歸算法

longFib(longn){

if(n<=1)returnn;

elsereturnFib(n-1)+Fib(n-2);}

如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義

求解斐波那契數(shù)列的調(diào)用次數(shù)

NumCall(k)=2*Fib(k+1)-1。斐波那契數(shù)列的遞歸調(diào)用樹(shù)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)調(diào)用次數(shù)NumCall(k)=2*Fib(k+1)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)棧結(jié)點(diǎn)ntagtag=1,向左遞歸；tag=2,向右遞歸Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(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-241n=1sum=1+142n=4-2Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(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+0Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)longFibnacci(longn){ Stack<Node>S;Node*w;longsum=0;

//反復(fù)執(zhí)行直到所有終端結(jié)點(diǎn)數(shù)據(jù)累加完

do{

while(n>1){

w->n=n;w->tag=1;S.push(w);n--;}

//向左遞歸到底,邊走邊進(jìn)棧

sum=sum+n;

//執(zhí)行求和

longFibnacci(longn){

while(!S.IsEmpty()){ w=S.getTop();S.Pop();

if(w->tag==1){//改為向右遞歸

w->tag=2;S.push(w);n=w->n–2;

//F(n)右側(cè)為F(n-2)

break;} } }while(!S.IsEmpty()); returnsum;}while(!S.IsEmpty())單向遞歸用迭代法實(shí)現(xiàn)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;}單向遞歸用迭代法實(shí)現(xiàn)longFibIter(longvoidrecfunc(intA[],intn){if(n>=0){

cout<<A[n]<<“”;n--;recfunc(A,n);}}

2536721899495463

尾遞歸用迭代法實(shí)現(xiàn)voidrecfunc(intA[],intvoidsterfunc(intA[],intn){//消除了尾遞歸的非遞歸函數(shù)

while(n>=0){cout<<"value"<<A[n]<<endl;n--;

}}

voidsterfunc(intA[],int遞歸與回溯

常用于搜索過(guò)程n皇后問(wèn)題 在n行n列的國(guó)際象棋棋盤(pán)上，若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線(xiàn)上，則稱(chēng)為它們?yōu)榛ハ喙?。n皇后問(wèn)題是指找到這

n個(gè)皇后的互不攻擊的布局。遞歸與回溯常用于搜索過(guò)程n皇后問(wèn)題1#主對(duì)角線(xiàn)3#主對(duì)角線(xiàn)5#主對(duì)角線(xiàn)0#次對(duì)角線(xiàn)2#次對(duì)角線(xiàn)4#次對(duì)角線(xiàn)6#次對(duì)角線(xiàn)1#次對(duì)角線(xiàn)3#次對(duì)角線(xiàn)5#次對(duì)角線(xiàn)0#主對(duì)角線(xiàn)2#主對(duì)角線(xiàn)4#主對(duì)角線(xiàn)6#主對(duì)角線(xiàn)01230123k=i+jk=n+i-j-11#主對(duì)角線(xiàn)0#次對(duì)角線(xiàn)1#次對(duì)角線(xiàn)0#主對(duì)角線(xiàn)0解題思路安放第i行皇后時(shí)，需要在列的方向從0到n-1試探(j=0,…,n-1)在第

j列安放一個(gè)皇后：如果在列、主對(duì)角線(xiàn)、次對(duì)角線(xiàn)方向有其它皇后，則出現(xiàn)攻擊，撤消在第

j

列安放的皇后。如果沒(méi)有出現(xiàn)攻擊，在第

j

列安放的皇后不動(dòng)，遞歸安放第i+1行皇后。解題思路安放第i行皇后時(shí)，需要在列的方向從0到n-設(shè)置4個(gè)數(shù)組

col[n]

：col[i]標(biāo)識(shí)第i列是否安放了皇后

md[2n-1]:md[k]標(biāo)識(shí)第k條主對(duì)角線(xiàn)是否安放了皇后

sd[2n-1]:sd[k]標(biāo)識(shí)第k條次對(duì)角線(xiàn)是否安放了皇后

q[n]:q[i]記錄第i行皇后在第幾列設(shè)置4個(gè)數(shù)組voidQueen(inti){for(intj=0;j<n;j++){if(第i行第j列沒(méi)有攻擊

){

在第i行第j列安放皇后；

if(i==n-1)

輸出一個(gè)布局；

elseQueen(i+1

);}

撤消第i行第j列的皇后；

}}voidQueen(inti){算法求精voidQueen(inti){for(intj=0;j<n;j++){if(!col[j]&&!md[n+i-j-1]&&!sd[i+j]){

/*第i行第j列沒(méi)有攻擊*/

col[j]=md[n+i-j-1]=sd[i+j]=1;

q[i]=j;

/*在第i行第j列安放皇后*/

算法求精

if(i==n-1){/*輸出一個(gè)布局*/

for(j=0;j<n;j++)

cout<<q[j]<<‘,’;cout<<endl;}elseQueen(i+1

);}

col[j]=md[n+i-j-1]=sd[i+j]=0;

q[i]=0;/*撤消第i行第j列的皇后*/}}if(i==n-1){廣義表(GeneralLists)

廣義表的概念n(0)個(gè)表元素組成的有限序列，記作

LS=(a0,a1,a2,…,an-1)

LS是表名，ai是表元素，它可以是表(稱(chēng)為子表)，可以是數(shù)據(jù)元素(稱(chēng)為原子)。

n為表的長(zhǎng)度。n=0的廣義表為空表。

n>0時(shí)，表的第一個(gè)表元素稱(chēng)為廣義表的表頭(head)，除此之外，其它表元素組成的表稱(chēng)為廣義表的表尾(tail)。

廣義表(GeneralLists)廣義表的概念n廣義表的特性有次序性有長(zhǎng)度A=()B=(6,2)C=(‘a(chǎn)’,(5,3,‘x’))D=(B,C,A)E=(B,D)F=(4,F)有深度可共享可遞歸廣義表的特性有次序性A=()有深度可遞歸遞歸過(guò)程與遞歸工作棧課件廣義表的表示只包括整數(shù)和字符型數(shù)據(jù)的廣義表鏈表表示

表中套表情形下的廣義表鏈表表示5232436103914list25list11247‘a(chǎn)’‘s’廣義表的表示只包括整數(shù)和字符型數(shù)據(jù)的廣義表鏈表表示表中套表廣義表結(jié)點(diǎn)定義結(jié)點(diǎn)類(lèi)型utype=0,表頭；=1,整型原子；=2,字符型原子；=3,子表值value

utype=0時(shí),存放引用計(jì)數(shù)(ref)；utype=1時(shí),存放整數(shù)值(intinfo)；utype=2時(shí),存放字符型數(shù)據(jù)(charinfo)；utype=3時(shí),存放指向子表表頭的指針(hlink)尾指針tlink

utype=0時(shí),指向該表第一個(gè)結(jié)點(diǎn)；utype0時(shí),指向同一層下一個(gè)結(jié)點(diǎn)

utypevaluetlink

廣義表結(jié)點(diǎn)定義結(jié)點(diǎn)類(lèi)型utype=0,表頭；=1廣義表的存儲(chǔ)表示EBF011430133D0115132‘x’012‘a(chǎn)’3C013330116DBBCA1201A廣義表的存儲(chǔ)表示EBF011430133D0廣義表的類(lèi)定義classGenList;

//GenList類(lèi)的前視聲明classGenListNode{ //廣義表結(jié)點(diǎn)類(lèi)的前視聲明structItems{//僅有結(jié)點(diǎn)信息的項(xiàng)friendclassGenlistNode;friendclassGenlist;intutype; //＝0/1/2/3union{ //聯(lián)合

廣義表的類(lèi)定義classGenList; //GenLiintref;//utype=0,存放引用計(jì)數(shù)

intintinfo; //utype=1,存放整數(shù)值

charcharinfo;//utype=2,存放字符

GenListNode*hlink; //utype=3,存放指向子表的指針

}}

classGenListNode{ //廣義表結(jié)點(diǎn)類(lèi)定義friendclassGenlist;private:intutype; //＝0/1/2/3intref;//GenListNode*tlink; //下一結(jié)點(diǎn)指針

union{ //聯(lián)合

intref; //utype=0,存放引用計(jì)數(shù)

intintinfo; //utype=1,存放整數(shù)值

charcharinfo;//utype=2,存放字符

GenListNode*hlink; //utype=3,存放指向子表的指針

}value;public:GenListNode():utype(0),tlink(NULL),ref(0){}

//構(gòu)造函數(shù),建表頭結(jié)點(diǎn)GenListNode*tlink; //下一結(jié)GenListNode(intt,GenListNode*next=

NULL){}

//構(gòu)造函數(shù)：建表結(jié)點(diǎn)

Items&Info(GenListNode*elem); //返回表元素elem的值

intnodetype(GenListNode*elem)

{returnelem->utype;

}

//返回表元素elem的數(shù)據(jù)類(lèi)型

GenListNode&setInfo(Items&x);

//將表元素elem中的值修改為x};GenListNode(intt,GenLiclassGenList{

//廣義表類(lèi)定義

private:GenListNode*first;//廣義表頭指針

GenListNode*Copy(GenListNode*ls);

//復(fù)制一個(gè)ls指示的無(wú)共享非遞歸表

intdepth(GenListNode*ls); //計(jì)算由

ls

指示的非遞歸表的深度

intequal(GenListNode*s,GenListNode*t); //比較以s和t為表頭的兩個(gè)表是否相等

voidRemove(GenListNode*ls); //釋放以ls

為表頭結(jié)點(diǎn)的廣義表classGenList{ public:Genlist();

//構(gòu)造函數(shù)

~GenList(); //析構(gòu)函數(shù)

GenListNode&Head();//返回表頭元素

GenList&Tail(); //返回表尾

GenListNode*First(); //返回第一個(gè)元素

GenListNode*Next(GenListNode*elem); //返回表元素elem的直接后繼元素

voidsetNext(GenListNode*elem1,

GenListNode*elem2);

//將elem2插到表中元素elem1后

public:voidCopy(constGenList&l)