第 3 章(2)━━函数的递归调用、重载、默认参数.ppt

C 程序设计 第3章 2 函数的递归调用 重载 默认参数 主要内容 函数的递归调用递归函数的执行过程函数的重载重载函数的注意事项带默认值的形参内联函数程序的多文件结构编译预处理 函数的递归调用 函数的递归调用 直接递归调用 指在一个函数A的定义中 出现了调用自身A的情况 这种调用关系称为直接递归调用 而函数A就是递归函数 间接递归调用 指在一个函数A的定义中 调用了函数B 而在函数B的定义中又调用了函数A 这种调用关系称为间接递归调用 而函数A也是递归函数 递归算法的关键在于 确立递归的公式 分析递归的结束条件递归函数设计的一般方法 先判断递归结束条件 再进行递归调用 例 用递归算法求n 分析 确立递归公式 n n n 1 分析递归结束条件 当n 0或n 1时 n 的值为1 include includeintfun intn 函数fun 的功能是 求n if n 0 n 1 return1 先判断递归结束条件return n fun n 1 再进行递归调用 voidmain intn cout n if n 0 cout 输入数据有错 exit 0 cout n fun n endl 运行 请输入一个正整数 3 3 6 main 函数调用fun 3 时的执行过程 main 函数调用fun 3 时栈中的变化情况 递归函数的执行过程 递归函数的执行过程 递归函数的执行过程比较复杂 往往都存在着连续的递归调用 其执行过程可分为 递推 和 回归 两个阶段 先是一次一次不断的递推过程 直到符合递归结束条件 然后是一层一层的回归过程 而其中的每一次递归调用 系统都要在栈中分配空间以保存该次调用的返回地址 参数 局部变量 因此在递推阶段 栈空间一直处于增长状态 直到遇到递归结束条件 然后进入回归阶段 栈空间反向依次释放 在递归的执行过程中 递归结束条件非常重要 它控制 递推 过程的终止 因此在任何一个递归函数中 递归结束条件都是必不可少的 否则将会一直 递推 下去 导致无穷递归 递归算法的缺点 内存消耗巨大 且连续地调用和返回操作占用较多的CPU时间 递归算法的优点 算法描述简洁易懂 例 分析下面递归函数的执行过程 并给出程序运行结果 includevoidsub charc cout c if c a return sub c 1 cout c return voidmain charch e sub ch 运行 edcbabcde 例 用递归算法计算从n个人中选择k个人组成一个委员会的不同组合数 分析 确立递归的公式 由n人中选k人的组合数 由n 1人中选k人的组合数 由n 1人中选k 1人的组合数 分析递归的结束条件 当n k或k 0时 组合数为1 include includeintcomm intn intk 函数comm 的功能是 求n人中选k人的组合数 if n n k if n 0 k 0 cout 输入数据有错 exit 0 cout 由 n 人中选 k 人的组合数 comm n k endl 运行 请输入正整数n和k 85 由8人中选5人的组合数 56 例 汉诺塔问题 有A B C三根柱子 A柱上有n个大小不等的盘子 大盘在下 小盘在上 要求将这n个盘子从A柱移动到C柱 在移动的过程中可以借助A B C中任何一根柱子 但每次只允许移动一个盘子 且在移动过程中三根柱子上都必须保持大盘在下 小盘在上 分析 将n个盘子从A柱移动到C柱可分解为以下三个步骤 将A柱上n 1个盘子移动到B柱 借助C柱 将A柱上剩下的一个盘子移动到C柱上 将n 1个盘子从B柱上移动到C柱上 借助A柱 分析得到 以上三个步骤包含两种操作 将若干个盘子从一根柱上移动到另一根柱上 用递归函数hanoi 实现 将1个盘子从一根柱上移动到另一根柱上 用函数move 实现 includevoidmove charget charput 函数move 的功能是 将一个盘子从get柱上移动到put柱上cout get 柱 put 柱 endl voidhanoi intn charone chartwo charthree 函数hanoi 的功能是 将n个盘子从one柱移动到three柱 借助two柱 if n 1 move one three return 先判断递归结束条件else hanoi n 1 one three two 将one柱上n 1个盘子移动到two柱 借助three柱 进行递归调用move one three 将one柱上剩下的一个盘子移动到three柱上hanoi n 1 two one three 将two柱上n 1个盘子移动到three柱 借助one柱 进行递归调用 voidmain intn cout n cout 将 n 个盘子从A柱移动到C柱的步骤 endl hanoi n A B C 函数的重载 函数的重载 重载的含义 就是重新赋予新的含义 在C 的一个程序中可以用同一个函数名来命名多个函数 这些同名的函数在参数个数 类型上一定有所不同 分别代表不同的函数 当同名的多个函数出现在同一个作用域内时 称为重载函数 重载的目的 程序中经常将功能相近的函数在相同作用域内以相同函数名命名 从而形成重载函数 目的是方便使用 便于记忆 例 intadd intx inty floatadd floatx floaty floatadd doublex doubley intadd intx inty intadd intx inty intz intadd intx inty intz intw 重载函数的注意事项 注意事项 重载函数的形参必须有所不同 参数个数或参数类型不同 编译系统是根据实参与形参在类型及个数上的最佳匹配来选择调用哪一个函数 例 定义重载函数时 要避免二义性 以免编译系统无法确定到底调用哪一个函数 例 例 includeintadd intx inty 重载函数 cout 正在进行 两个int型数据相加 t t return x y floatadd floatx floaty 重载函数 cout 正在进行 两个float型数据相加 t t return x y doubleadd doublex doubley 重载函数 cout 正在进行 两个double型数据相加 t t return x y voidmain inta1 5 b1 8 floata2 5 1 b2 8 1 doublea3 5 2 b3 8 2 cout add a1 b1 endl cout add a2 b2 endl cout add a3 b3 endl cout add 2 4 endl cout add 2 1 4 1 endl cout add A 2 endl 运行 正在进行 两个int型数据相加 13正在进行 两个float型数据相加 13 2正在进行 两个double型数据相加 13 4正在进行 两个int型数据相加 6正在进行 两个double型数据相加 6 2正在进行 两个int型数据相加 115 带默认值的形参 默认形参值的作用 函数声明时可以给形参指定一个默认值 调用时若给出实参 则形参采用实参值 若没有给出相应的实参 则该形参采用预先给出的默认值 例 includeintadd intx 10 inty 20 带默认形参值的函数 cout 正在进行 x y return x y voidmain cout add 30 40 endl cout add 50 endl cout add endl cout add 2 4 endl cout add A 1 endl cout add A endl 运行 正在进行 30 40 70正在进行 50 20 70正在进行 10 20 30正在进行 50 4 54正在进行 65 49 114正在进行 65 20 85 带默认值的形参 带默认值的形参声明顺序 函数必须按从右往左的顺序逐一声明带默认值的形参 且在带默认值的形参右面不能出现不带默认值的形参 只有这样规定后 在函数调用时才不会产生二义性 例 带默认值的形参 默认形参值仅能声明一次 若函数定义在前 调用在后 默认形参值在函数定义时声明 若函数调用在前 定义在后 默认形参值必须在函数原型声明中给出 且在之后该函数定义时 不能再重复指定默认形参值 例 includeintadd intx 1 inty 2 带默认形参值的函数原型声明voidmain cout add 3 4 endl cout add 5 endl cout add endl intadd intx inty 函数的定义性声明 cout 正在进行 x y return x y 运行 正在进行 3 4 7正在进行 5 2 7正在进行 1 2 3 带默认值的形参 默认形参值的作用域 同一个函数在相同的作用域内 默认形参值应保持唯一 但在不同的作用域内 可提供不同的默认形参值 例 includeintadd intx 1 inty 2 函数add 的全局原型声明voidmain intadd intx 3 inty 4 函数add 局部原型声明voidfun 函数fun 的原型声明cout add endl 使用局部默认形参值 实现3 4 fun voidfun 函数fun 的定义性声明 cout add endl 使用全局默认形参值 实现1 2 cout add 10 endl intadd intx inty 函数add 的定义性声明 cout 正在进行 x y return x y 运行 正在进行 3 4 7正在进行 1 2 3正在进行 10 2 12 内联函数 内联函数 含义 函数声明时前面加上inline为内联函数 含义是向编译系统建议 编译时在调用处用函数体进行置换 以节省了函数调用时控制转移 参数传递等开销 实质 是使用空间换取时间的方法 以加速程序的执行 当出现多次调用同一个内联函数时 程序本身占用的空间有所增加 若内联函数仅调用一次时 并不增加程序本身占用的存储空间 注意 对于用户指定的内联函数 编译器是否作为内联函数来处理由编译器自行决定 另外内联函数体内不能有循环 switch等复杂的结构控制语句 例 includeinlinefloatarea floatr 内联函数 return 3 1415 r r voidmain cout 半径 3 n面积 area 3 endl cout 半径 5 n面积 area 5 endl 运行 半径 3面积 28 2735半径 5面积 78 5375 程序的多文件结构 多文件的程序 在C 中 一个较大的程序通常被分解为若干个源程序文件 然后分别对各个源程序文件单独进行编译 这些源程序文件由一个工程文件进行管理 最后连接成一个完整的程序 在多文件组成的程序中 一个源程序文件中定义的全局变量或函数 在另外一个源程序文件中被引用前 必须先对该全局变量或函数作外部声明 外部类型变量的声明格式 extern类型全局变量名 外部类型函数的声明格式 extern函数的原型声明 若一个源程序文件中定义的全局变量或函数 仅限于该源程序文件中使用 不能被程序中的其他源程序文件使用 在定义该全局变量或函数时前面需加上static 内部类型变量的声明格式 static类型全局变量名 内部类型函数的声明格式 static函数的原型声明 例 本程序由两个文件组成 c1 cpp c2 cpp 文件c1 cpp内容 includeinta 5 定义a为一般全局变量 可拓展到外部文件使用staticintb 8 定义b为静态全局变量 只能在本文件中使用externintf0 intx 函数f0 的外部声明 其定义部分在c2 cpp中intf1 intx inty 函数f1 的定义性声明 可拓展到外部文件使用 cout 进入函数f1 了 t return x y a b externintf2 intx 函数f2 的外部声明 其定义部分在c2 cpp中externintf3 函数f3 的外部声明 其定义部分在c2 cpp中externintf4 intx inty 函数f4 的外部声明 其定义部分在c2 cpp中voidmain cout f0 7 endl 此句编译通过 但连接出错 f0 仅能在c2 cpp中使用cout f1 1 2 endl cout f2 3 endl cout f3 endl cout f4 5 6 endl 运行 进入函数f1 了 16进入函数f2 了 15进入函数f3 了 进入函数f0 了 216进入函数f4 了 180 文件c2 cpp内容 includeexterninta 全局变量a的外部声明 其定义部分在c1 cpp中externintb 全局变量b的外部声明 其定义部分在c1 cpp中staticintf0 intx 函数f0 的定义性声明 只能在本文件中使用 cout 进入函数f0 了 t return x x intf2 intx 函数f2 的定义性声明 可拓展到外部文件使用 cout 进入函数f2 了 t b 此句编译通过 但连接出错 b仅能在c1 cpp中使用return x a intf3 函数f3 的定义性声明 可拓展到外部文件使用 cout 进入函数f3 了 t return f0 a a intf4 intx inty 函数f4 的定义性声明 可拓展到外部文件使用 cout 进入函数f4 了 t return x y a 编译预处理 编译预处理 指源程序文件在被编译之前 由编译预处理程序对其所做的加工处理工作 编译预处理程序不是C 编译程序的组成部分 编译预处理程序在处理源程序文件时 是将预处理好的程序写入到一个临时文件中 并将该临时文件作为编译程序的输入文件 即编译程序是对该临时文件进行编译 产生目标文件 编译预处理不会影响源程序文件中的内容 编译预处理命令 一律以 开头 以回车符结束 末尾不加分号 且单独占用一行 编译预处理命令通常放在源程序文件的开始部分 编译预处理命令有三种 包含文件 宏定义 条件编译 编译预处理 include命令 包含文件 格式1 include格式2 include 文件名 处理过程 将命令中所指定的文件内容嵌入到当前源程序文件的该 include命令处 成为当前源程序文件的一个组成部分 include 表示按标准方式查找 即从C 系统目录下的include子目录中开始查找所要包含的文件 C 的库函数一般都存放在编译器约定的include子目录下 当需要使用库函数时通常采用该格式 include 文件名 表示先从当前目录 即当前源程序文件所在的目录 开始查找所要包含的文件 若找不到 再按标准方式查找 到C 系统目录下的include子目录中继续查找 当需要包含用户自定义的文件时 通常采用该格式 include 带路径的文件名 若所要包含的文件既不在include子目录中 也不在当前目录中 必须指明文件的路径 例 include E ABC 123 file1 编译预处理 define命令 不带参数的宏定义 格式1 define宏名格式2 define宏名宏体 处理过程 定义一个宏名 若宏名后面跟有宏体 则将其后程序中所有出现该宏名的地方用相应的宏体替换之 这种替换过程称为 宏替换 或 宏展开 几点说明 宏名是一个标识符 通常用大写字母表示 以便与程序中的变量名区别 宏定义可以出现在程序中的任何位置 宏名的作用域是从定义处开始到文件结尾处结束 若要提前终止宏名的作用域 可使用预处理命令 undef宏名 在同一个作用域内 同一个宏名不允许定义两次或两次以上 否则编译预处理在进行宏替换时 会出现二义性 在一个宏定义中可以使用前面已定义过的宏名 编译预处理 define命令 宏替换时 只对宏名做简单的替换 不做任何计算 也不做任何语法检查 若宏定义时书写不正确 会得到不正确的结果或编译时出现语法错误 当宏名出现在字符串中时 编译预处理不进行宏替换 例 include defineA3 5 defineBA A 替换后 defineB3 5 3 5 defineC A A 替换后 defineC 3 5 3 5 defineD A defineE 输出 t voidmain cout E B南C京A endl 替换后 cout 输出 t B南C京A endl cout E A endl 替换后 cout 输出 t 3 5 endl cout E B endl 替换后 cout 输出 t 3 5 3 5 endl cout E C endl 替换后 cout 输出 t 3 5 3 5 endl cout E D endl 替换后 cout 输出 t A endl 运行 输出 B南C京A输出 8输出 23输出 64输出 A 编译预处理 define命令 带参数的宏定义 格式 define宏名 形参表 宏体形参表 由若干个参数名组成 参数之间以逗号分隔 宏体 由若干个参数组成的一个式子 处理过程 类似于函数的处理过程 先将宏调用中的实参替换宏定义中的形参 即先进行参数的替换 再进行宏替换 几点说明 宏名是一个标识符 与后面形参表的左括号之间不得有空格 所谓参数的替换 是指用宏调用中的每一个实参字符序列去替换宏定义中的相应形参 且只做简单的替换 不做任何计算 一个宏定义应在一行内定义完 以换行符结束 若多于一行在行尾加上转义符 例 include definePRINT a cout x y PRINT x 替换后 cout a x endl PRINT y 替换后 cout a y endl PRINT x y 替换后 cout a x y endl PRINT 1 2 替换后 cout a 1 2 endl print x y 替换后 cout a b x y endl cout a b x y endl print 2 6 4 7 替换后 cout a b 2 6 4 7 endl cout a b 2 6 4 7 endl 运行 请输入两个整数 85 a 8a 5a 13a 3a b 40a b 1a b 33a b 10 编译预处理 条件编译命令 使用宏名作为程序段是否被编译的条件 格式1 ifdef宏名格式3 ifndef宏名程序段程序段 endif endif格式2 ifdef宏名格式4 ifndef宏名程序段1程序段1 else else程序段2程序段2 endif endif 作用 通常源程序中的所有语句都将被编译 但有时希望源程序中的某个程序段只有在满足某种条件时才被编译 而条件不满足时则不被编译 就好像该程序段从源程序中消失了一样 此时可选用上面格式之一来实现有条件的编译 编译预处理 条件编译命令 几点说明 以格式1为例 当源程序中使用 ifdef宏名 程序段 endif结构时 若该程序段要被编译 可在该结构的前面加上一条定义宏名的预处理命令 define宏名 若该程序段不被编译 则将其前面的宏名定义命令删除掉 删除 define宏名 这种做法比从源程序中将