第3章讲 栈与队列.ppt

* 3. 问题的解法是递归的 汉诺塔(Tower of Hanoi)问题的解法： 如果 n = 1，则将这一个盘子直接从 A 柱移到 C 柱上。否则，执行以下三步： 用 C 柱做过渡，将 A 柱上的 (n-1) 个盘子移到 B 柱上； 将 A 柱上最后一个盘子直接移到 C 柱上； 用 A 柱做过渡，将 B 柱上的 (n-1) 个盘子移到 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和返回地址 返回地址用行编号表示 n x y z 返回地址 main() { int m; printf(Input number of disks:”); scanf(%d,m); 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) } * 构成递归的条件 不能无限制地调用本身，必须有一个出口，化简为非递归状况直接处理。 Procedure name ( parameter list ) { if ( initial condition ) //递归结束条件 return ( initial value ); else //递归 return (name ( parameter exchange )); } * 递归过程在实现时，需要自己调用自己。 层层向下递归，退出时的次序正好相反： 递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序 主程序第一次调用递归过程为外部调用； 递归过程每次递归调用自己为内部调用。 它们返回调用它的过程的地址不同。 3.2.2递归过程与递归工作栈 * long Factorial(long n) { int temp; if (n == 0) return 1; else temp = n * Factorial(n-1); return temp; } void main() { int result; result = Factorial(4); cout result endl; } RetLoc1 RetLoc2 * 1. 递归工作栈 每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。 每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。 栈顶的工作记录是当前正在执行的这一层的工作记录。称之为活动记录。 局部变量 返回地址 参 数 活动记录框架 递归 工作记录 * 函数递归时的活动记录 ………………. 下一条指令 Function(参数表) ………………. return 调用块 函数块 返回地址(下一条指令) 局部变量 参数 * 计算Fact时活动记录的内容p106 递归调用序列 0 temp RetLoc2 1 temp RetLoc2 2 temp RetLoc2 3 temp RetLoc2 4 temp RetLoc1 参数 返回值 返回地址 返回时的指令 return