第八章. 函数.ppt

假如不模块化 读多少行的程序能让你不头疼？ main( )当中能放多少行程序？ 假如printf()函数由10行代码替换，那么你见过的程序会成什么样子？ 如果所有代码都在main()当中，怎么团队合作？ 如果代码都在一个文件中，怎么团队合作？ 模块化的优点 模块各司其职 每个模块只负责一件事情，它可以更专心 便于进行单个模块的设计、开发、调试、测试和维护等工作 一个模块一个模块地完成，最后再将它们集成 开发人员各司其职 按模块分配任务，职责明确 并行开发，缩短开发时间 分而治之（Wirth, 1971 ）信息隐藏（Parnas, 1972） 函数（function）和模块（module） 函数是C语言中模块化编程的最小单位 可以把每个函数看作一个模块 若干相关的函数可以合并作一个“模块” 【例8.7】有5个人，第5个人说他比第4个人大2岁，第4个人说他对第3个人大2岁，第3个人说他对第2个人大2岁，第2个人说他比第1个人大2岁，第1个人说他10岁。求第5个人多少岁 通过分析，设计递归函数如下： 10 (n=1) age(n)= age(n-1)+2 (n1) 例8.8（自学） 求整数n的阶乘n！分析比较： 例 8.8 求整数n的阶乘n！ #include stdio.h main() { int n, i; long result=1; printf(Input n:); scanf(%d, n); result = 1; for (i=1; i=n; i++) result *= i; printf(%d!= %ld, n, result); } 例 8.8求整数n的阶乘n！ 例 8.8求整数n的阶乘n！ #include stdio.h long fact(long n); main() { int n; long result; printf(Input n: ); scanf(%d, n); result = fact(n); if(result == -1) printf(n0,data error ! \ n); else printf(%d! = %ld\n, n, result); } 递归调用过程 执行过程： fact(5)=5*fact(4) fact(4)=4*fact(3) fact(3)=3*fact(2) fact(2)=2*fact(1) fact(1)=1 递归函数 递归方法的基本原理 将复杂问题逐步化简，最终转化为一个最简单的问题 最简单问题的解决，就意味着整个问题的解决 递归调用应该能够在有限次数内终止递归 递归调用如果不加以限制，将无数次的循环调用 必须在函数内部加控制语句，只有当满足一定条件时，递归终止 有时将其称为条件递归 递归函数 任何一个递归调用程序必须包括两部分 递归循环继续的过程 递归调用结束的过程 if (递归终止条件成立) return 递归公式的初值; else return 递归函数调用返回的结果值; 例8.9（自学） 汉诺塔问题 “汉诺塔”（Hanoi） 这是一个必须用递归方法才能解决的问题 n=64时， 18,446,744,073,709,551,615次 1844亿亿次 每次1微秒，需要60万年 递归问题的提出 A→C，A→B，C→B， A→C，B→A，B→C，A→C 递归问题的提出 A→C，A→B，C→B， A→C，B→A，B→C，A→C 递归问题的提出 A→C，A→B，C→B， A→C，B→A，B→C，A→C 递归问题的提出 A→C，A→B，C→B， A→C，B→A，B→C，A→C 递归问题的提出 A→C，A→B，C→B， A→C，B→A，B→C，A→C 递归问题的提出 第一步：将问题简化。 假设A杆上只有2个圆盘，即汉诺塔有2层，n＝2。 递归问题的提出 对于一个有 n（n1）个圆盘的汉诺塔，将n个圆盘分为两部分：上面的 n-1 个圆盘和最下面的n号圆盘。将“上面的n-1个圆盘”看成一个整体。 将 n-1个盘子从一根木桩移