数据结构栈与递归含分治与回溯课件.ppt

《数据结构栈与递归含分治与回溯课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、什么是递归main函数{……调用函数f……}f函数{……调用函数g……}g函数{………………}f函数{……调用函数f……}递归调用函数调用递归指函数直接或间接调用自己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

2、*3+11←6←2←1←24←120返址nr5671234利用递归可方便地解决很多普通方法无法求解的问题显式递归问题，如求Fibnacci数列F(n)=F(n-1)+F(n-2)递归公式；F(1)=1,F(2)=1边界条件intf(intn){if(n==1

3、

4、n==2)r=1;//写f(n)=1错elser=f(n-1)+f(n-2);//注意returnr;}3、如何用递归递归求解的关键是找边界条件和递归关系编写递归函数，根据边界条件和递归关系是否明显可将问题分为显示递归和隐式递归两类，前者可直接写出递归函数，

5、后者要通过认真分析找到边界条件，并通过降阶+分治+回溯找递归关系边界条件递归公式隐式递归—降阶EdouardLucas1842-1891,FrenchABC每次只移一个盘大盘不能压小盘类似数学归纳法，假设f(n-1)已知，在此基础上考虑f(n)的求法,如Hannoi塔问题XYZ边界条件:if(n==1)printf(“%c→%c”,x,z);XYZ降阶:假设能把n-1个盘从一个位置移动到另一个位置则...hanoi(n,x,y,z);降阶：分三步hanoi(n-1,x,z,y);printf(“%c→%c”,x,z

6、);hanoi(n-1,y,x,z);递归函数：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);xyzABCvoidhanoi(intn,charx,chary,charz){if(n==1)printf(“%c→%c”,x,z);else{hanoi(n-1,x,z,y);printf(“%c→%c”,x,z);

7、hanoi(n-1,y,x,z);}}voidmain(){hanoi(3,’A’,’B’,’C’);}A→CA→BC→BA→CB→AB→CA→C递归函数中要有使递归趋于结束的边界条件对于Fibnacci数列中F(n)=F(n-1)+F(n-2)形式的递归公式，分析求f(5)的过程可知f(1)被多次重复调用，因此原因，求F(40)在Core2T5500CPU上约费20秒时间，故此类问题要避免递归，需用非递归算法改写递归—参考书参考”关于递归教学的探讨.doc”注意事项：隐式递归—分治--树的相关操作intTreeD

8、epth(TreeT){//求二叉树深if(T==NULL)d=0;else{d1=TreeDepth(T->lchild1);d2=TreeDepth(T->rchild);if(d1>d2)d=d1+1;elsed=d2+1;}returnd;}一棵树由根结点、左子树及右子树组成，对树的操作可分成对根、左子树和右子树的操作来完成！6/5-43-12*+隐式递归—回溯--8皇后问题终态易判定,递归过程记录完整解,回溯输出.Go-VerifyintGo(intarr[N][N],inti)//逐行处理，当前处理编号

9、为i的行{intj;for(j=0;j

10、结束i=N-1）则输出解，所有解！PrintChessBoard(arr);return1;}}if(j==N)return-1;}voidmain(){inta[N][N]={0};Go(a,0);}voidPrintChessBoard(inta[N][N]){inti,j;for(i=0;i