栈与递归--含分治与回溯

《栈与递归--含分治与回溯》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3.3栈与递归什么是递归？为何用递归？如何用递归？递归实现原理---栈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、为何用递归与递归执行过程很多问题能够用递归的方式描述,此时根据递归边界和递归公式构造出递归函数即可求解

2、,如f(1)=1f(n)=n*F(n-1)3+4*3+3*3+2*6+5*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塔问题ABC降阶:假设能把n-1个盘从一个位置移动到另一个位置则...hanoi(intn,charx,chary,charz);降阶：分三步hanoi(n-1,x,z,y);printf(“%c→%c”,x,z);hanoi(n-1,y

6、,x,z);XYZ边界条件:if(n==1)printf(“%c→%c”,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”,

7、x,z);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”及“函数作业说明.doc”作业2：7.8将代码写入作

8、业本注意事项：理解递归的概念及其执行过程递归求解的关键是找递归边界和递归关系的定义。对显式递归问题会直接写出递归求解函数，对于简单的隐式递归问题会通过降阶找递归关系和递归边界递归执行效率偏低，能用递推或其它方法求解尽量不用递归，此外，要避免递归重复现象的发生函数及递归常见错误intf(intn){if(n==1)f(n)=1;elsef(n)=n*f(n-1);returnf(n);}intf(intn,intr){intr;if(n==1)r=1;elser=n*f(n-1);returnr;}隐式递归—分治--树的相关操作intTreeDepth

9、(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皇后问题voidNQueens(intarr[N][N],inti){intj;for(j=0;j

10、rify(arr,i)==0){arr[i][j]=0;continue;}elseif(i==N-1){P