数据结构与算法-栈和队列2

华中农业大学理学院章英zy@

数据结构与算法

1/39第六讲递归算法本讲知识点：(1)了解递归的特点(2)掌握递归向非递归转换的方法

(3)了解栈在处理递归问题中的应用重点：递归思路分析难点：栈在递归向非递归转换中的应用2/39一、递归递归是程序设计中最有力的方法之一。优点：采用递归编出的程序简洁、清晰，程序结构符合结构化程序设计，可读性好。问题：编译程序是如何处理这类带有递归调用功能的程序的？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？3/39数学中常常利用递归手段来定义一些概念，如求阶乘的运算。n的阶乘定义为：

n*(n–1)!n>0n!=

1n=0求阶乘4/39递归算法longf(intn){longp;if(n==0)return1;elsereturnn*f(n-1);}voidmain(){longx=f(4);

cout<<x;}递归项终止项5/39longf(intn){longp;if(n==0)return1;elsereturnn*f(n-1);}voidmain(){longx=f(3);

cout<<x;}123n=34567longf(intn){longp;if(n==0)return1;elsereturnn*f(n-1);}n=2891011longf(intn){longp;if(n==0)return1;elsereturnn*f(n-1);}n=112131415longf(intn){longp;if(n==0)return1;elsereturnn*f(n-1);}n=016171819带回了12122带回了12324带回了627282920带回了225266/39调用前：（1）将所有的实参、返回地址传递给被调用函数保存（2）为被调用函数的局部变量分配存储区（3）将控制转移到被调用函数入口。调用后：（1）保存被调用函数的计算结果。（2）释放被调用函数的数据区（3）依照被调用函数保存的返回地址将控制转移到调用函数函数调用的过程7/39整数划分问题递归法求解排列组合设m.n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。

例：f(5,3)=5，

5

种表示方式：

3+2

3+1+1

2+2+1

2+1+1+1

1+1+1+1+1参看s3/partition.cpp8/39相同的问题:m个苹果放到n个盘子上，问有多少种放法?整数划分问题9/39递归出口：没有苹果或者盘子只剩下1个 则只有1种方法整数划分问题5个苹果放到1个盘子里，只有1种放法10/39递归项：(1)苹果数少于盘子数 等价于去掉多余的盘子整数划分问题×5个苹果放到6个盘子里的放法，等价于5个苹果放到5个盘子里的放法11/39递归项：(2)苹果数多于盘子数

a：至少有1个盘子空着的放法加上b：所有盘子都有苹果的放法整数划分问题a：5个苹果放到4个盘子里，至少有1个盘子空着的放法， 就是5个苹果放到3个盘子里的放法12/39递归项：(2)苹果数多于盘子数

a：至少有1个盘子空着的放法加上b：所有盘子都有苹果的放法整数划分问题b：既然所有盘子都有苹果，可以把每个盘子里的苹果拿走一个， 就是1个苹果放到4个盘子的放法13/39int

f(intm,intn)

{

if(m==0||n==1)return

;

//没有苹果或者盘子剩下1个

if(m<n)return

;

//苹果数少于盘子数，只需要相同的盘子数就足够了

if(m==n)return1+

;

//苹果数和盘子数相等，b所有盘子都有苹果，和a至少有1个盘子空着，可取消这条语句

returnf(m,n-1)+f(m-n,

);

//苹果数多于盘子数，a+b

}

递归实现14/39int

f(intm,intn)

{

if(m==0||n==1)return1;

if(m<n)return

f(m,m);

if(m==n)return1+f(m,n-1);

returnf(m,n-1)+f(m-n,n);}

递归实现参考答案参看s3/apple.cpp15/39递归过程f(5,3)=f(5,2)+f(2,3)=f(5,1)+f(3,2)+f(2,3)

=1+f(3,1)+f(1,2)+f(2,3) =1+1+f(1,1)+f(2,3) =1+1+1+f(2,2)=1+1+1+1+f(2,1)=1+1+1+1+1=5具体打印形式的输出，请参考partitio.cpp，运用2个栈来输出各种表示方法。16/39分为：(1)在求解过程中直接求值，无需回溯。称这类递归问题为简单递归问题；(2)另一类递归问题在求解过程中不能直接求值，必须进行试探和回溯，称这类递归问题为复杂递归问题求解方法：(1)简单递归问题可以采用递推方法直接求解；(2)复杂递归问题由于要进行回溯，在实现过程中必须借助栈来管理和记忆回溯点。

二、递归分类17/39已知勒让德多项式的递归定义如下：

1n=0

pn(x)=xn=1

((2n-1)xpn-1(x)(n-1)pn-2(x))/nn>1

简单递归问题例如：求P3(3)P0(3)=1

P1(3)=3P1(3)=3

P2(3)=13P2(3)=(3*3*3-1)/2=13P3(3)=(5*3*13-2*3)/3=6318/39floatp(intn,floatx)

{

floatp1,p2;

if(n==0)return(1.0);

//终止条件

elseif(n==1)return(x);

//终止条件

else{

p1=(2*n-1)*x*p(n-1,x);

p2=(n-1)*p(n-2,x);

return((p1-p2)/n);

}

}递归实现19/39分析问题用两个变量pre1,pre2，记录递推关系的子问题的解p(i,x)=((2i-1)xp(i-1,x)(i-1)p(i-2,x))/ipre1=p(i-2,x)

pre2=p(i-1,x)当求出第i阶多项式的值后，i值加1，需要修改pre1和pre2。则用pre1记录pre2当前的值，而用pre2记录新求出的多项式的值。直到i=n。递推关系式：20/39floatp(intn,floatx)

{

floatpre1,pre2,a,b,valuep;

inti;

if(n==0)return(1.0);

elseif(n==1)return(x);//接下一页非递归实现参看s3/legendre.cpp21/39

else{

pre1=1.0;

pre2=x;

for(i=2;i<=n;++i)

{

a=2*i-1;

b=i-1;

valuep=(a*pre2*x-b*pre1)/i;

pre1=pre2;

pre2=valuep;

}

return(valuep);

}

}非递归实现22/39迷宫是实验心理学中一个古典问题。以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。入口在左上方（1，1）处，出口在右下方（m，n）处。要求：求出从迷宫入口到出口有无通路，若有通路则指出其中一条通路的路径。

复杂递归问题23/3901234567890123456789入口出口4R3D5L6U24/3915L16L26U25R24R34U33R32R22D12D11R按照RDLU方向进行探索第一方向R探路成功右边是墙，第二方向D探路成功右边是墙，第二方向D探路成功第一方向R探路成功第一方向R探路成功右下墙，左已经在栈里表明在路上，U第一方向R探路成功第一方向R探路成功右下墙，左已经在栈里表明在路上，U右墙，下已经在栈里表明在路上，L右下已经在栈里表明在路上，L25/3915L16L26U25R24R34U33R32R22D12D11R按照RDLU方向进行探索14四个方向均失败，标记死路，栈顶看15L的下一个方向U是否可行，墙只有退栈，并标记15死路，看16L的方向U，不行，退栈，标记死路，看26，不行，退栈，标记死路……26/39//迷宫行走路线存储专用栈类

classstack_for_maze{private:

structnode//结点用来记录压栈的迷宫坐标

{ intx;

inty; chardirection;//上一步的行走方向（即如何来到这里的）→←↑↓

node*next; }; node*head;算法分析27/39public: stack_for_maze(){//构造函数

head=NULL; } ~stack_for_maze()

//析构函数 { node

*p=head; while(head!=NULL) { head=head->next; deletep; p=head; } }算法分析28/39voidpush(intxx,

intyy,

charddirection){ node*new_node; new_node=newnode; if(new_node!=NULL) { new_node->x=xx; new_node->y=yy; new_node->direction=ddirection; new_node->next=NULL;

if(head==NULL)

head=new_node; else { new_node->next=head; head=new_node; } } else

cout<<"因为内存分配失败导致本次压栈失败！";}算法分析29/39node*pop(int

&xx,int

&yy)//出栈时带回栈顶元素坐标{ if(head!=NULL) { node*p=head; head=head->next; xx=p->x; yy=p->y; deletep; } else { cout<<"\n因为栈已空导致本次出栈失败\n"; } returnhead;}算法分析30/39voidprint()

//输出栈内元素{ if(head!=NULL) { node*p=head; while(p!=NULL) { cout<<“”<<p->x<<“”<<p->y;

cout<<“”<<p->direction<<endl; p=p->next; } } else cout<<"\n栈为空，打印失败\n";}};

//栈类的定义结束算法分析31/39voidCreateMaze()//创建迷宫{ intmax_way=MAX_X*MAX_Y;

//400 intx,y; for(x=0;x<MAX_X;x++) for(y=0;y<MAX_Y;y++) maze[x][y]=1;

//0~19都是墙壁 srand((unsigned)time(NULL)); for(inti=0;i<=max_way;i++) { x=rand()%(MAX_X-2)+1; y=rand()%(MAX_Y-2)+1; maze[x][y]=0;

//0表示可走的路 } maze[1][1]=0;

//入口 maze[MAX_X-2][MAX_Y-2]=0;

//[18][18]出口 maze[0][1]=8;

maze[MAX_X-1][MAX_Y-2]=0;

//maze[19][18]}32/39voidPrintMaze()

//输出迷宫的当前状态{

intx,y;

system(“cls”);

cout<<endl;

for(x=0;x<MAX_X;x++)

{

for(y=0;y<MAX_Y;y++)

｛ if(maze[x][y]==0){cout<<"";continue;}//通路

if(maze[x][y]==1){cout<<"■";continue;}//墙 if(maze[x][y]==2){cout<<"×";continue;}//死胡同 if(maze[x][y]==3){cout<<"↓";continue;}//向下走 if(maze[x][y]==4){cout<<"→";continue;}//向右走 if(maze[x][y]==5){cout<<"←";continue;}//向左走 if(maze[x][y]==6){cout<<"↑";continue;}//向上走 if(maze[x][y]==7){cout<<"※";continue;}//当前站立位置 if(maze[x][y]==8){cout<<"";continue;}//通路

}

cout<<endl;

}

Sleep(200);//延时函数}33/39voidmain(){

CreateMaze(); //创建迷宫

PrintMaze(); //输出当前迷宫的初始状态

stack_for_mazestack; //定义一个栈的对象，用来记录行走路线

move(stack); //行走中……

PrintMaze(); //输出迷宫的最终状态

stack.print();}算法分析34/39voidmove(stack_for_maze&s){ intx=1,y=1;//出发点

while(1) { maze[x][y]=2;

if(maze[x][y+1]==0)//→ { s.push(x,y,‘R'); //当前位置压栈

maze[x][y]=4;

y=y+1;//向右走到一个新位置

maze[x][y]=7;

PrintMaze();

if((x==MAX_X-1)&&(y==MAX_Y-2)) { s.push(x,y,'*');

cout<<"\n成功走出！！！\n"; return; } else continue; }35/39 //省