数据结构栈与递归含分治与回溯

数据结构栈与递归含分治与回溯第1页，共17页，2023年，2月20日，星期六1、什么是递归main函数{……

调用函数f……}f函数{……

调用函数g……}g函数{………………}f函数{……

调用函数f……}递归调用函数调用递归指函数直接或间接调用自己第2页，共17页，2023年，2月20日，星期六intf(intn){intr;if(n==1)r=1;elser=n*f(n-1);returnr;}voidmain(){intx;x=f(5);printf(“%d”,x);}2、为何用递归与递归执行过程很多问题能够用递归的方式描述，此时采用递归算法求解直观容易，如求阶乘：F(1)=1;F(n)=n*F(n-1)3+4*3+3*3+2*6+5*3+11←

6←

2← 1←

24←

120返址nr5671234利用递归可方便地解决很多普通方法无法求解的问题第3页，共17页，2023年，2月20日，星期六显式递归问题，如求Fibnacci数列F(n)=F(n-1)+F(n-2)递归公式；F(1)=1,F(2)=1边界条件intf(intn){if(n==1||n==2)r=1;//写f(n)=1错elser=f(n-1)+f(n-2);//注意returnr;}3、如何用递归递归求解的关键是找边界条件和递归关系编写递归函数，根据边界条件和递归关系是否明显可将问题分为显示递归和隐式递归两类，前者可直接写出递归函数，后者要通过认真分析找到边界条件，并通过降阶+分治+回溯找递归关系边界条件递归公式第4页，共17页，2023年，2月20日，星期六隐式递归—降阶EdouardLucas

1842-1891,FrenchABC每次只移一个盘大盘不能压小盘类似数学归纳法，假设f(n-1)已知，在此基础上考虑f(n)的求法,如Hannoi塔问题第5页，共17页，2023年，2月20日，星期六XYZ边界条件: if(n==1)printf(“%c→%c”,x,z);第6页，共17页，2023年，2月20日，星期六XYZ降阶:假设能把n-1个盘从一个位置移动到另一个位置则...hanoi(n,x,y,z);降阶：分三步hanoi(n-1,x,z,y);printf(“%c→%c”,x,z);hanoi(n-1,y,x,z);第7页，共17页，2023年，2月20日，星期六递归函数：hanoi(intn,charx,chary,charz)基始条件:if(n==1)printf(“%c→%c”,x,z);降阶：分三步hanoi(n-1,x,z,y);printf(“%c→%c”,x,z);hanoi(n-1,y,x,z);xyz第8页，共17页，2023年，2月20日，星期六ABCvoidhanoi(intn,charx,chary,charz){if(n==1)printf(“%c→%c\n”,x,z);else{hanoi(n-1,x,z,y);printf(“%c→%c\n”,x,z);hanoi(n-1,y,x,z);}}voidmain(){hanoi(3,’A’,’B’,’C’);}A→

CA→

BC→

BA→

CB→

AB→

CA→

C第9页，共17页，2023年，2月20日，星期六递归函数中要有使递归趋于结束的边界条件对于Fibnacci数列中F(n)=F(n-1)+F(n-2)形式的递归公式，分析求f(5)的过程可知f(1)被多次重复调用，因此原因，求F(40)在Core2T5500CPU上约费20秒时间，故此类问题要避免递归，需用非递归算法改写递归—参考书参考”关于递归教学的探讨.doc”注意事项：第10页，共17页，2023年，2月20日，星期六隐式递归—分治--树的相关操作intTreeDepth(TreeT){//求二叉树深 if(T==NULL)d=0; else{

d1=TreeDepth(T->lchild1);

d2=TreeDepth(T->rchild);if(d1>d2)

d=d1+1; else d=d2+1; } returnd;}一棵树由根结点、左子树及右子树组成，对树的操作可分成对根、左子树和右子树的操作来完成！6/5-43-12*+第11页，共17页，2023年，2月20日，星期六隐式递归—回溯--8皇后问题终态易判定,递归过程记录完整解,回溯输出.Go-Verifyint

Go(intarr[N][N],inti)//逐行处理，当前处理编号为i的行{

intj;

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

{

arr[i][j]=1;//尝试在第i行的第j列摆下一个棋子;intsuccessFlag=Verify(arr,i);

if(successFlag==0){arr[i][j]=0;continue;}

elseif(successFlag==1&&i<N-1){//验证合法则前进到下一行

//仅当从当前布局前进得不到结果时重布局if(Go(arr,i+1)==1)return1;else{arr[i][j]=0;continue;}

}

else{//验证合法且（到达结束i=N-1）则输出解，所有解！

PrintChessBoard(arr);return1;

}

}if(j==N)return-1;}voidmain(){ inta[N][N]={0}; Go(a,0);}第12页，共17页，2023年，2月20日，星期六voidPrintChessBoard(inta[N][N]){ inti,j; for(i=0;i<N;i++) { for(j=0;j<N;j++) { printf("%3d",a[i][j]); } printf("\n"); } printf("\n\n");}intVerify(inta[N][N],inti){ intsum,j,k; for(j=0;j<N;j++)//逐列检查 { sum=0; for(k=0;k<=i;k++)//看当前列前i行中是否冲突 { sum+=a[k][j]; } if(sum>1)return0; } return1;}第13页，共17页，2023年，2月20日，星期六隐式递归—回溯（全部解）voidGo(intarr[N][N],inti)//逐行处理，当前处理编号为i的行{

for(intj=0;j<N;++j)

{

arr[i][j]=1;//尝试在第i行的第j列摆下一个棋子;successFlag=Verify(arr,i);

if(successFlag==0){arr[i][j]=0;continue;}

elseif(successFlag==1&&i<N-1){//验证合法则前进到下一行

Go(arr,i+1);arr[i][j]=0;continue;

//不管成功与否都重置

}

else{//验证合法且到终态（i=N-1）则输出解。输出所有解！

PrintChessBoard(arr);arr[i][j]=0;continue;

}

}}voidmain(){ inta[N][N]={0}; Go(a,0);}第14页，共17页，2023年，2月20日，星期六4、递归原理与实现—栈系统在函数调用前完成的工作：将返回地址等信息入栈，并保存本层局部变量值为被调函数的局部变量分配存储区将控制转移到被调函数代码区的入口系统在被调函数返回之前完成的工作：保存被调函数的计算结果释放被调函数的数据区出栈并根据返回地址将控制转移到调用函数,恢复执行递归作为函数调用特例过程同上，允许递归的语言中系统自动维护一个递归工作栈,不支持递归时用户可仿照系统自行设立递归工作栈第15页，共17页，2023年，2月20日，星期六intf(intn){1intr;2if(n==1)r=1;3elser=n*f(n-1);4returnr;}voidmain(){5intx;6x=f(5);7print(x);}3+4*3+3*3+2*6+5*3+11←

6←

2← 1←

24120返址nr利用栈将递归化为非递归举例：intf(intn){

SElemTypee,temp;

SqStackS; InitStack(S); while(n>1){//递归前进，入栈 e.n=n; Push(S,e); n--; } e.n=1;e.r=1;Push(S,e);//边界条件 while(!StackEmpty(S)){//递归后退