C语言学习笔记 八—— 函数与递归

内容函数思想、函数定义与调用、函数声明、栈与内存布局、递归。引言一个较大的程序一般应分为若干个程序模块每一个模块用来实现一个特定的功能。所有的高级语言中都有子程序这个概念用子程序实现模块的功能。在C语言中子程序的作用是由函数来完成的。一个C程序可由一个主函数和若干个其他函数构成。由主函数调用其他函数其他函数也可以互相调用。同一个函数可以被一个或多个函数调用任意多次。在程序开发中常将一些常用的功能模块编写成函数放在公共函数库中供大家选用。程序设计人员要善于利用函数以减少重复编写程序段的工作量。一、为什么需要函数背景举例ATM 机插卡(检测) → 操作界面 → 输入密码 → 验证 → 主界面 → 点击存钱 → 驱动存钱窗口 → 放钱(数验) → 确认 → 结束思想自上而下逐步拆解。把大问题拆成小问题小问题再拆成更小的问题——更小的问题往往对应一个简单独立的功能。函数提供了实现功能的语法一个函数就是完成一个功能的独立、单一。比如getchar/putchar、scanf/printf、rand()、strcpy、strcmp、strcat。二、函数的定义2.1 函数模型输入 → 处理 → 输出2.2 语法类型标识符 函数名(形式参数) { 函数体 // 声明部分 // 语句部分 }四个组成部分类型标识符数据类型反映函数带出来的结果的类型注意不能是数组类型函数名标识符命名规则和变量名一致函数名一般反映函数功能形式参数函数要处理的数据数据来源是实际给到的参数即实参函数体完成函数功能的那部分代码。2.3 例子两个整数求和Step1确定函数名与功能相关——add/sum。Step2从输入-处理-输出角度确定形参。【考虑要处理哪些数据个数哪种类型的数据数据类型】两个整数求和 → 两个形参都是 int形参格式数据类型 形参变量名1, 数据类型 形参变量名2, ... 注意每个形参变量都要说明类型。 int a, int bStep3处理数据核心功能result a b;Step4返回值类型就是整型用return (表达式);返回结果。intsum(inta,intb){intresult;resultab;returnresult;}三、函数的调用3.1 语法函数名(实际参数)调用方式有三种函数调用语句函数调用表达式作函数调用的实参。3.2 练习找两个数中的最大值intmax(inta,intb){intret0;if(ab){reta;}else{retb;}returnret;}3.3 完整示例add.c#includestdio.h// 函数定义intsum(inta,intb){intresultab;returnresult;}intmax(inta,intb){intret0;if(ab){reta;}else{retb;}returnret;}intmaxf(floata,floatb);// 函数声明函数定义在 main 之后intmain(void){// 函数调用intretsum(1,2);printf(ret %d\n,ret);floata0,b0;printf(Input two num:);scanf(%f%f,a,b);printf(max %d\n,maxf(a,b)*2);// 调用作表达式return0;}intmaxf(floata,floatb)// 函数头 函数体{floatret0;if(ab){reta;}else{retb;}returnret;}四、函数的位置与声明函数定义可以放在main 函数之前——同时起到定义和声明的效果函数定义放在main 函数之后——需要在使用之前做函数声明。函数声明把函数头复制一份末尾加上分号;intmaxf(floata,floatb);// 函数声明注意C 语言中标识符一定要先声明、后使用。五、注意事项实参和形参每个形参变量都要说明类型实参和形参做到个数相同、类型匹配、一一对应返回值类型如果不写默认是 int 类型返回值类型与返回结果类型不一致时以返回值类型为准如果函数不需要传入数据形参设计为void返回值如果没有也设计为void。void 例子打印 MP3 菜单voidprintMenu(void){printf(----MP3-----\n);printf(Play\n);printf(Next\n);return;// 返回值类型为 void 时可以有 return但后面什么值都不要写}六、例子函数6.1 判断素数intisPrime(intnum){// 返回 1 表示真返回 0 表示假}6.2 完整示例test_prime.c判断素数 打印 100 以内素数#includestdio.hintisPrime(intn){inti0;intret1;for(i2;in;i){if(n%i0){ret0;break;}}returnret;}voidprintPrimeInX(intn){inti0;for(i2;in;i){if(isPrime(i)1){printf(%d ,i);}}putchar(\n);}intmain(void){intn0;printf(Input a num:);scanf(%d,n);printPrimeInX(n);return0;}七、函数的好处降低重复代码的编写提高编程效率实现程序的模块化提高程序的可靠性和可维护性。八、练习8.1 判断闰年// 闰年条件year%100 ! 0 year%4 0 || year%400 0intisLeapYear(intyear){returnyear%100!0year%40||year%4000;}8.2 获得月份天数test_year.c#includestdio.hintisLeapYear(intyear){returnyear%100!0year%40||year%4000;}intgetDaysMonth(inty,intm){if(m1||m12){return-1;}intmon[12]{31,28,31,30,31,30,31,31,30,31,30,31};// 2 月要根据闰年多 1 天其余月份直接取数组returnm2?mon[m-1]isLeapYear(y):mon[m-1];}intmain(void){intyear,month;printf(Input a year and month:);scanf(%d%d,year,month);printf(days %d\n,getDaysMonth(year,month));return0;}九、函数嵌套调用与内存布局9.1 嵌套调用关系isPrime { } printPrimeInX { isPrime(); } main { printPrimeInX(); }注意main函数称为程序的入口函数函数可以实现嵌套调用所有程序的运行都在内存上运行。9.2 栈栈是一种数据结构数据组织方式本身是一块内存空间。特点先进后出 FILO类比一筒羽毛球入栈、出栈局部变量都放在栈上栈上变量特点自动申请、自动释放Linux 系统栈空间默认 8M可以修改。9.3 C 程序内存布局[栈] // 局部变量自动申请自动释放先进后出 [堆] // 特别大手动申请手动释放 [全局区/静态区] // 存放全局变量或静态变量 [字符串常量区] // hello [代码区] // 代码程序 代码 数据。堆区特点特别大手动申请、手动释放。32 位系统下地址总线 32 位4G 地址空间操作系统约占 1G。十、递归10.1 什么是递归自己调用自己就是递归。直接递归voidfunc1(void){func1();// 直接调用自己}间接递归voidfunc2(void){func1();}voidfunc1(void){func2();}10.2 递归的特点自己调用自己递归是一种特殊的循环for / while / do-while。从效率上说for / while / do-while 效率更高但有些问题用递归更容易实现递归解决问题是倒着思考的解决问题 n看看问题 n-1 能不能解决还需要知道问题 n 和 n-1 之间的递推关系实现递归需要问题 n 和问题 n-1 之间的递推关系递归结束条件注意递归深度不要太深太深栈空间不够会导致段错误。10.3 例 1123…100sum(n) sum(n-1) n sum(100) └─ sum(99) 100 └─ sum(98) 99 └─ sum(97) 98 └─ ... └─ sum(1) 2 └─ 1 ← 结束条件intsum(intn){if(n1)// 递归结束条件{return1;}else{returnsum(n-1)n;// 递推关系}}10.4 例 2n!fact(n) fact(n-1) * n fact(1) 1intfact(intn){if(n1){return1;}else{returnfact(n-1)*n;}}10.5 例 3斐波那契数列1 1 2 3 5 8 13 ...规律前两项固定是 1从第三项开始每一项都是它前两项之和fibo(n) fibo(n-1) fibo(n-2)结束条件n 1 || n 2。intfibo(intn){if(n2||n1){return1;}else{returnfibo(n-1)fibo(n-2);}}10.6 递归完整代码diGui.c#includestdio.hvoidfunc1(void){printf(hello world!\n);func1();// 直接递归没有结束条件会死循环直到栈溢出}intsum(intn){if(n1){return1;}else{returnsum(n-1)n;}}intfact(intn){if(n1){return1;}else{returnfact(n-1)*n;}}intfibo(intn){if(n2||n1){return1;}else{returnfibo(n-1)fibo(n-2);}}intmain(void){intn0;scanf(%d,n);// printf(sum %d\n, sum(n));// printf(ret %d\n, fact(n));printf(ret %d\n,fibo(n));return0;}十一、[小结]函数思想自上而下、逐步拆解函数定义函数调用函数的位置使用前要先出现先声明后使用。十二、作业封装一个函数求两个数的最大公约数再封装一个函数求两个数的最小公倍数//封装一个函数判断一个数是不是素数#includestdio.hintisPrime(intn){inti;intret1;//把返回值设定为1if(n1)//1不是素数{return0;}for(i2;in;i)//除去1和数本身在中间找有没有约数{if(n%i0)//除以这个数能除得尽说明不是素数{ret0;//返回值改变break;}}returnret;}intmain(void){inti0;for(i1;i98;i){if(isPrime(i)isPrime(i2)){printf(%d %d \n,i,i2);}}return0;}封装一个函数判断一个数是否为素数并利用该函数找出 0~100 以内的双胞胎素数两个素数相差为 2例如3 5、5 7。// 最小公倍数递归求法#includestdio.hintmaxY(inta,intb){//先找最大公约数if(b0){returna;}else{returnmaxY(b,a%b);}}intminB(inta,intb){//最小公倍数 两数的乘积 除以 两数的最大公约数returna*b/maxY(a,b);}intmain(void){inta,b;printf(Input tow num : );scanf(%d %d,a,b);printf(最大公约数 %d\n,maxY(a,b));printf(最小公倍数 %d\n,minB(a,b));return0;}