3.3栈与递归.ppt

3.3 栈与递归;递归算法的编写 1）将问题用递归的方式描述（定义） 2）根据问题的递归描述（定义）编写递归算法 问题的递归描述（定义） 递归定义包括两项 基本项（终止项）：描述递归终止时问题的求解； 递归项：将问题分解为与原问题性质相同，但规模较小的问题； 例 阶乘函数 　n!= 1* 2* 3* 4 * (n-1)* n 　n!递归定义 　n!= 1 当 n=1 时 　　　　　　　n!= n (n-1)! 当n 1 时;计算5的阶乘（5！=5X4X3X2X1） int f(int n) { if ( n = = 1) return (1); else return ( n * f(n-1)); };void print(int w) { int i; if ( w!=0) { print(w-1); for(i=1;i=w;++i) printf(“%3d,”,w); printf(“/n”); } };递归调用执行情况如下：;假设有A、B、C三个轴。在A上插有n个直径大小不同、以小到大编号为1、2、…、n的圆盘。现要求将A轴上的n个圆盘移至C轴上，并按同样顺序叠排。移动圆盘的规则为： 1）每次只能移动一个圆盘； 2）圆盘可以插在A、B、C的任意一个上； 3）任何时刻都不能将较大的圆盘压在较小的圆盘之上。 注： 这是一个经典的递归问题，n阶问题可以分解为n圆盘和n-1阶问题。;A;A B C;A B C;解决方法： n=1时，直接把圆盘从A移到C n1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。 即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题 执行情况： 递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示; main() { int m; printf(Input number of disks”); scanf(%d,n); printf(”Steps : %3d disks”,n); hanoi(n,A,B,C); (0) } void hanoi(int n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z); (4) else{ (5) hanoi(n-1,x,z,y); (6) move(n,x,z); (7) hanoi(n-1,y,x,z); (8) } (9) }; main() { int m; printf(Input the number of disks scanf(%d,m); printf(The steps to moving %3d hanoi(m,A,B,C); (0) } void hanoi(int n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z); (4) else{ (5) hanoi(n-1,x,z,y); (6) move(n,x,z); (7) hanoi(n-1,y,x,z); (8) } (9) }; main() { int m; printf(Input the number of disks scanf(%d,m); printf(The steps to moving %3d hanoi(m,A,B,C); (0) } void hanoi(int n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z); (4) else{ (5) hanoi(n-1,