C语言程序设计-提高篇-第5节 递归共同体.ppt

C语言程序设计—提高篇 例1：用递归求阶乘的算法。 long int fact(int n) { int x; long int y; if (n==0) return 1; /*定义递归出口将1返回给fact(0)*/ y=fact(n-1)*n; return(y); } void main() { long int fn; fn=fact(5); printf(\nfn=%ld\n,fn); } * ——提高篇 第5章 递归、共同体和枚举 内容概述 递归 共同体 枚举　 教学目标 掌握递归的概念与应用； 牢记共用体变量的定义，并能正确地使用； 描述枚举类型的定义及使用方法 。 5.1递归 定义 所谓“递归”就是允许程序调用自己本身的过程或函数。 构成递归需具备的条件 1. 子问题须与原始问题为同样的事，且更为简单； 2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。 递归不是一种数据结构，而是一种有效的算法设计 注意：递归算法必须是逐步有规律简化的，最终要有一个非递归的出口，不能出现无穷调用的情况。 阶乘的递归定义 （1） 5！=5 × 4！ （2） 　　4！=4 × 3！ （3） 3！=3 ×2！ （4） 2！=2 ×1！ （5） 1！=1 × 0！ （6） 0！=1 （a） if（n= =0） fact = 1；/*定义出口*/ else { （b） x= n - 1； （c） 求出y=x！； /*顺序递推求解*/ （d） fact = n * y； /*回溯递推求值*/ } 程序实现递归阶乘算法的伪程序 long int fact（int n） { int x； long int y； if (n==0) return 1； x=n-1； y=fact（x）； return（n*y）； } 例1：用递归求阶乘的算法。 #include stdio.h void main() { long int fn； fn=fact(5)； printf(”\nfn=%ld”，fn); } 求解阶乘 5! 的过程 主程序 main : fact(5) 参数 5 计算 5*fact(4) 返回 120 参数 4 计算 4*fact(3) 返回 24 参数 3 计算 3*fact(2) 返回 6 参数 2 计算 2*fact(1) 返回 2 参数 1 计算 1*fact(0) 返回 1 参数传递 结果返回 递归调用 回归求值 参数 0 直接定值 = 1 返回 1 n=5 5! 5*4! 4*3! 3*2! 2*1! 1 1 1*2 2*3 6*4 24*5 120 回推 递推 递归结束条件 n!= (n=1) n*(n-1)! (n1) 函数的递归调用 递归调用——函数直接或间接调用自身。 递归函数——这种调用自身的函数为递归函数。 递归算法的设计 具有某种可借用类同自身的子问题描述的性质。 相对于问题来说,子问题将更加简化。 某一有限步的子问题有直接的解存在。 例2：Hanoi塔 假设有三根木桩分别为A、B和C。在木桩A上安置了N个圆盘，由上到下编号为1，2，…N，编号越大的圆盘直径也越大。现需要将A木桩上的N个圆盘借助B木桩移到C木桩上，且必须按照下述移动规则： 1. 直径较小的圆盘永远置于直径比较大的圆盘上; 2. 圆盘可任意地由任何一个木桩移到其他的木桩上; 3. 一次只能移动一个盘子。 汉诺塔(Tower of Hanoi)问题的解题思路： 如果 n=1，则将这一个盘子直接从A柱移到C柱上。否 则，执行以下三步： 1.用C柱做过渡，将A柱上的(n-1)个盘子移到B柱上； 2.将A柱上最后一个盘子直接移到C柱上； 3.用A柱做过渡，将B柱上的(n-1)个盘子移到C柱上。 #include stdio.h void Hanoi(int n,char x,char y,char z) { if(n==1) printf(Move disk %d from %c to %c\n,n,x,z); else { Hanoi(n-1, x, z, y); printf(Move disk %d from %c to %c\n,