《栈与递归--含分治与回溯》由会员分享，可在线阅读，更多相关《栈与递归--含分治与回溯（17页珍藏版）》请在金锄头文库上搜索。
1、3.3 栈与递归,什么是递归？ 为何用递归？ 如何用递归？ 递归实现原理-栈,1、什么是递归,main函数 调用函数f ,f 函数 调用函数g ,g 函数 ,f 函数 调用函数f ,递归调用,函数调用,递归指函数直接或间接调用自己,递归调用边界,递归公式(关系),int f ( int n ) int r;if(n= =1) r=1;else r=n*f (n-1);return r; ,void main( ) int x;x=f(5);printf(“%d”,x); ,2 、为何用递归与递归执行过程,很多问题能够用递归的方式描述, 此时根据递归边界和递归公式构造出递归函数即可求解,如f(1
2、)=1f(n)=n*F(n-1),3+ 4 *,3+ 3 *,3+ 2 *,6+ 5 *,3+ 1 1, 6, 2, 1, 24, 120,返址 n r,5 6 7,1 2 3 4,利用递归可方便地解决很多普通方法无法求解的问题,显式递归问题，如求Fibnacci数列F(n)=F(n-1)+F(n-2)递归公式；F(1)=1,F(2)=1边界条件,int f ( int n ) if(n= =1|n= =2)r=1;/写f(n)=1错,是调用非变量 elser=f (n-1)+f (n-2);/注意！return r; ,3、如何用递归,递归求解的关键是找边界条件和递归关系编写递归函数，根据边
3、界条件和递归关系是否明显可将问题分为显示递归和隐式递归两类，前者可直接写出递归函数，后者要通过认真分析找到边界条件，并通过降阶+分治+回溯找递归关系,边界条件,递归公式,隐式递归降阶,Edouard Lucas 1842-1891,French,A,B,C,每次只移一个盘 大盘不能压小盘,类似数学归纳法，假设f(n-1)已知，在此基础上考虑f(n)的求法,如Hannoi塔问题,A,B,C,降阶:假设能把n-1个盘从一个位置移动到另一个位置则.,hanoi(int n,char x,char y,char z); 降阶：分三步 hanoi(n-1, x, z, y); printf(“%c%c”
4、,x,z); hanoi(n-1, y, x, z);,X,Y,Z,边界条件:if(n= =1) printf(“%c%c”,x,z);,递归函数：,hanoi(int n, char x,char y, char z) 基始条件: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);,x,y,z,A,B,C,void hanoi(int n, char x, char y, char z) if(n= =1)printf(“%c%cn”,x,z);else
5、hanoi(n-1, x, z, y);printf(“%c%cn”,x,z);hanoi(n-1, y, x, z); void main( ) hanoi(3,A,B,C); ,A C A B C B A C B A B C A C,递归函数中要有使递归趋于结束的边界条件 对于Fibnacci数列中F(n)=F(n-1)+F(n-2)形式的递归公式，分析求f(5)的过程可知f(1)被多次重复调用，因此原因，求F(40)在Core2 T5500CPU上约费20秒时间，故此类问题要避免递归，可用非递归算法改写递归 后续内容仅供参考，学习数据结构时细学！ 参考”关于递归教学的探讨.doc”及“函
6、数作业说明.doc” 作业2：7.8将代码写入作业本,注意事项：,理解递归的概念及其执行过程 递归求解的关键是找递归边界和递归关系的定义。对显式递归问题会直接写出递归求解函数，对于简单的隐式递归问题会通过降阶找递归关系和递归边界 递归执行效率偏低，能用递推或其它方法求解尽量不用递归，此外，要避免递归重复现象的发生 函数及递归常见错误,int f ( int n ) if(n= =1) f(n)=1;else f(n)=n*f (n-1);return f(n); ,int f ( int n ,int r) int r;if(n= =1) r=1;else r=n*f (n-1);return
7、 r; ,隐式递归分治,-树的相关操作,int TreeDepth(Tree T)/递归求树深if(T=NULL)d=0;elsed1=TreeDepth(T-lchild1);d2=TreeDepth(T-rchild);if(d1d2)d=d1+1;elsed=d2+1;return d; ,一棵树由根结点、左子树及右子树组成，对树的操作可分成对根、左子树和右子树的操作来完成！,隐式递归回溯,-8皇后问题,void NQueens(int arrNN,int i) int j;for (j = 0; j1) /递归前进，入栈e.n=n; Push(S,e);n=e.n-1;e.n=1;e.
8、r=1;Push(S,e); /边界条件while(!StackEmpty(S) /递归后退，出栈Pop(S,e);if(!StackEmpty(S) /计算下层rGetTop(S,temp);temp.r=temp.n*e.r;SetTopElem(S,temp);/递归结束return e.r;/返回结果 /更多可参考相关论文,递归函数中要有使递归趋于结束的边界条件 对于Fibnacci数列中F(n)=F(n-1)+F(n-2)形式的递归公式，分析求f(5)的过程可知f(1)被多次重复调用，因此原因，求F(40)在Core2 T5500CPU上约费20秒时间，故此类问题要避免递归，需用非递归算法改写递归参考书 思考：递归求解迷宫问题.回溯+算法演示系统 作业：3.7+3.15,注意事项：,
