内蒙古机电职业技术学院.doc

内蒙古机电职业技术学院 《C语言程序设计》教案 PAGE PAGE 1 内蒙古机电职业技术学院 教 案 首 页 课程：c语言程序设计 授课顺次：7 学时：2 班级：计信、自动化 日期： 第 节 课 题 4.3递归调用 目的要求 让学生掌握递归的概念 2、让学生掌握递归调用 重点难点 1、C语言的直接递归调用 教学过程 后附 教学手段 教学方法：讲授、演示 教学媒体：多媒体教学网 课后分析 以讲述理论知识为主，多举实例。 4.3 递归调用 递归：问题的求解归为更简单问题的求解（但不能直接求得） 递推：从一个已知事实出发，按一定规律推出下一事实，再以此为新事实，推出下一个事实。函数调用函数本身，称为函数的递归调用。 函数直接调用本身，称直接递归。 函数调用其它函数，其它函数又调用了本函数，称为间接递归。 递归调用形式如下: (1) 直接递归 void a( ) { ...… a ( ); / * 自己调用自己, 直接递归 */ ..… }(2) 间接递归 void a( ) { ...… b ( ); / * 调用函数b * ...… } void b( ) { a ( ); /* 调用函数a, 间接递归 */ .. } 例4.8 用递归算法计算n！ 讨论：我们曾用循环的方法实现了n！计算，现在采用递归的方法计算。n！本身就是以递归的形式定义的: n= n * (n-1)! n0 编程: if (初始条件) 表达式; else 递推表达式; #include unsigned long fac(unsigned int n) { unsigned long f ; if (n==0) f=1; /*递归结束条件*/ else f = n * fac(n-1); /*直接递归调用*/ return f; } main( ) { unsigned long y; unsigned int n; scanf(“%u”, n); y = fac(n); printf(“%u!=%lu”, n, y); } 分析:当程序输入3时 例4.9 写递归函数求mn,并在主函数中键盘输入m,n,调用函数求mn的值 main() {int m,n; printf(Input m,n:); scanf(%d,%d,m,n); printf(%3d^%-d=%-d\n,m,n,power(m,n)); } power(int x,int y) {int p; if (y==0) p=1; else p=x*power(x,y-1); return p; } 例4.10 汉诺塔游戏 用递归算法来做汉诺塔游戏的程序是很有趣的，可以使复杂的过程变得意想不到的简单。汉诺塔（Tower of Hanoi）游戏据说来源于布拉玛神庙。 底座上有三根金刚石的针，第一根针上放着从大到小64个金片。游戏的目标是把所有金片从第一根针移到第三根针上，第二根针作为中间过渡。每次只能移动一个金片，并且大的金片不能压在小的金片上面。该游戏的结束就标志着“世界末日”的到来。 游戏中金片移动是一个很繁琐的过程。通过计算，对于64个金片至少需要移动 264 – 1 = 1.8×1019 次 。 对于把n（n1）个金片从第一根针a上移到第三根针c的问题可以分解成如下步骤: (1) 将n-1个金片从a经过c 移动到b。 (2) 将第n个金片移动到c。 (3) 再将n-1个盘子从b经过a移动到c。 void hanoi(int n, int a, int b, int c) { if （n==0） return； /* 0个金片不处理 */ if (n==1) printf(%d -%d\n,a,c); /* n=1时, 直接将金片从a移动到c */ else { hanoi(n-1,a,c,b); /* 先将n-1个金片从a经过c 移动到b */ printf(%d -%d\n,a,c); /* 将第n个金片从a移动到c */ hanoi(n-1,b,a,c); /* 再将n-1个金片从b经过a移动到c */ } } 主函数如下： #include main( ) { int n; printf(Input n:); scanf(%d,n); hanoi(n,1,2,3);/*n个金片从第一根针经过第二根针移动到第三根针上*/ }