程序设计（清华第二版）公开课第8章 函数课件

8 1概述8 2函数定义的一般形式8 3函数参数和函数的值8 4函数的调用8 5函数的嵌套调用8 6函数的递归调用8 7数组作为函数参数8 8局部变量和全局变量8 9变量的存储类别8 10内部函数和外部函数8 11如何运行一个多文件的程序习题 第8章函数 8 1概述 一个较大的程序一般应分为若干个程序模块 每一个模块用来实现一个特定的功能 所有的高级语言中都有子程序这个概念 用子程序实现模块的功能 在 语言中 子程序的作用是由函数完成的 一个 程序可由一个主函数和若干个函数构成 由主函数调用其他函数 其他函数也可以互相调用 同一个函数可以被一个或多个函数调用任意多次 图8 1是一个程序中函数调用的示意图 在程序设计中 常将一些常用的功能模块编写成函数 放在函数库中供公共选用 要善于利用函数 以减少重复编写程序段的工作量 先举一个简单的函数调用的例子 例8 1main printstar 调用printstar函数 print message 调用printmessage printstar 调用printstar函数 printstar printstar函数 printf n print message print message函数 printf Howdoyoudo n 运行情况如下 Howdoyoudo 图8 1 printstar和print message都是用户定义的函数名 分别用来输出一排 号和一行信息 说明 1 一个源程序文件由一个或多个函数组成 一个源程序文件是一个编译单位 即以源程序为单位进行编译 而不是以函数为单位进行编译 2 一个 程序由一个或多个源程序文件组成 对较大的程序 一般不希望全放在一个文件中 而将函数和其他内容 如预定义 分别放在若干个源文件中 再由若干源文件组成一个C程序 这样可以分别编写 分别编译 提高调度效率 一个源文件可以为多个C程序公用 3 程序的执行从main函数开始 调用其他函数后流程回到main函数 在main函数中结束整个程序的运行 main函数是系统定义的 4 所有函数都是平行的 即在定义函数时是互相独立的 一个函数并不从属于另一函数 即函数不能嵌套定义 这是和PASCAL不同的 函数间可以互相调用 但不能调用main函数 5 从用户使用的角度看 函数有两种 标准函数 即库函数 这是由系统提供的 用户不必自己定义这些函数 可以直接使用它们 应该说明 不同的C系统提供的库函数的数量和功能不同 当然有一些基本的函数是共同的 用户自己定义的函数 用以解决用户的专门需要 6 从函数的形式看 函数分两类 无参函数 如例8 1中的printstar和print message就是无参函数 在调用无参函数时 主调函数并不将数据传送给被调用函数 一般用来执行指定的一组操作 例如 例8 1那样 printstar函数的作用是输出18个星号 无参函数可以带回或不带回函数值 但一般以不带回函数值的居多 有参函数 在调用函数时 在主调函数和被调用函数之间有数据传递 也就是说 主调函数可以将数据传给被调用函数使用 被调用函数中的数据也可以带回来供主调函数使用 类型标识符函数名 声明部分语句 例8 1中的printstar和print message函数都是无参函数 用 类型标识符 指定函数值的类型 即函数带回来的值的类型 无参函数一般不需要带回函数值 因此可以不写类型标识符 例8 1就如此 8 2函数定义的一般形式1 无参函数的定义形式 类型标识符函数名 形式参数表列 声明部分语句 例如 intmax intx inty int 函数体中的声明部分 x y x y return 2 有参函数定义的一般形式 这是一个求x和y二者中大者的函数 笫1行第一个关键字int表示函数值是整型的 max为函数名 括号中有两个形式参数x和y 它们都是整型的 在调用此函数时 主调函数把实际参数的值传递给被调用函数中的形式参数x和y 花括弧内是函数体 它包括声明部分和语句部分 在声明部分定义所用的变量 此外对将要调用的函数作声明 见8 4 3节 在函数体的语句中求出 的值 为x与y中大者 return z 的作用是将 的值作为函数值带回到主调函数中 return后面的括弧中的值 z 作为函数带回的值 或称函数返回值 在函数定义时已指定max函数为整型 在函数体中定义 为整型 二者是一致的 将 作为函数max的值带回调用函数 见例8 2 如果在定义函数时不指定函数类型 系统会隐含指定函数类型为int型 因此上面定义的max函数左端的int可以省写 3 可以有 空函数 它的形式为类型说明符函数名 例如 dummy 调用此函数时 什么工作也不做 没有任何实际作用 在主调函数中写上 dummy 表明 这里 要调用一个函数 而现在这个函数没有起作用 等以后扩充函数功能时补充上 在程序设计中往往根据需要确定若干模块 分别由一些函数来实现 而在第一阶段只设计最基本的模块 其他一些次要功能或锦上添花的功能则在以后需要时陆续补上 在编写程序的开始阶段 可以在将来准备扩充功能的地方写上一个空函数 函数名取将来采用的实际函数名 如用merge matproduct oncatenate shell 等 分别代表合并 矩阵相乘 字符串连接 希尔法排序等 只是这些函数未编好 先占一个位置 以后用一个编好的函数代替它 这样做 程序的结构清楚 可读性好 以后扩充新功能方便 对程序结构影响不大 空函数在程序设计中常常是有用的 4 对形参的声明的传统方式在老版本C语言中 对形参类型的声明是放在函数定义的笫2行 也就是不在笫1行的括号内指定形参的类型 而在括号外单独指定 例如上面定义的max函数可以写成以下形式 intmax x y 指定形参x y intx y 对形参指定类型 intz z x y x y return z 一般把这种方法称为传统的对形参的声明方式 而把前面介绍过的方法称为现代的方式 TurboC和目前使用的多数C版本对这两种方法都允许使用 两种用法等价 NSI新标准推荐前一种方法 即现代方式 它与PASCAL语言中所用的方法是类似的 本书中的程序采用新标准推荐的现代方式 但由于有些过去写的书籍和程序使用传统方式 因此读者应对它有所了解 以便能方便地阅读它们 8 3 1形式参数和实际参数在调用函数时 大多数情况下 主调函数和被调用函数之间有数据传递关系 这就是前面提到的有参函数 前面已提到 在定义函数时函数名后面括弧中的变量名称为 形式参数 简称 形参 在主调函数中调用一个函数时 函数名后面括弧中的参数 可以是一个表达式 称为 实际参数 简称 实参 例8 2调用函数时的数据传递 main inta b c 8 3函数参数和函数的值 scanf d d a b c max a b printf axis d c max intx inty 定义有参函数max int x y x y return 运行情况如下 7 8 axis8程序中第7 12行是一个函数定义 注意第7行的末尾没有分号 第7行定义了一个函数名max和指定两个形参x y及其类型 程序第4行是一个调用函数语句 max后面括弧内的a b是实参 a和b是main函数中定义的变量 x和y是函数max中的形式参数 通过函数调用 使两个函数中的数据发生联系 见图8 2 图8 2关于形参与实参的说明 1 在定义函数中指定的形参 在未出现函数调用时 它们并不占内存中的存储单元 只有在发生函数调用时 函数max中的形参才被分配内存单元 在调用结束后 形参所占的内存单元也被释放 2 实参可以是常量 变量或表达式 如 max 3 a b 但要求它们有确定的值 在调用时将实参的值赋给形参 如果形参是数组名 则传递的是数组首地址而不是数组的值 请参阅8 7节 3 在被定义的函数中 必须指定形参的类型 见例8 2程序第7行 4 实参与形参的类型应相同或赋值兼容 例8 2中实参和形参都是整型 这是合法的 正确的 如果实参为整型而形参x为实型 或者相反 则按第2章介绍的不同类型数值的赋值规则进行转换 例如实参值a为3 5 而形参x为整型 则将实数3 5转换成 整数3 然后送到形参b 但此时应将max函数放在main函数的前面或在main函数中对被调用函数max作原型声明 否则会出错 关于对函数的声明见8 4 3小节 字符型与整型可以互相通用 5 语言规定 实参变量对形参变量的数据传递都是 值传递 即单向传递 只由实参传给形参 而不能由形参传回来给实参 这是和 T N不同的 在内存中 实参单元与形参单元是不同的单元 如图8 3所示 图8 3图8 4在调用函数时 给形参分配存储单元 并将实参对应的值传递给形参 调用结束后 形参单元被释放 实参单元仍保留并维持原值 因此 在执行一个被调用函数时 形参的值如果发生改变 并不会改变主调函数的实参的值 例如 若在执行函数过程中x和y的值变为10和15 而a和b仍为2和3 见图8 4 8 3 2函数的返回值通常 希望通过函数调用使主调函数能得到一个确定的值 这就是函数的返回值 例如 例8 2中 max 2 3 的值是3 max 5 2 的值是5 赋值语句将这个函数值赋给变量c 下面对函数值作一些说明 1 函数的返回值是通过函数中的return语句获得的 return语句将被调用函数中的一个确定值带回主调函数中去 见图8 2中从return语句返回的箭头 如果需要从被调用函数带回一个函数值 供主调函数使用 被调用函数中必须包含return语句 如果不需要从被调用函数带回函数值可以不要return语句 一个函数中可以有一个以上的return语句 执行到哪一个return语句 哪一个语句起作用 return语句后面的括弧也可以不要 如return 它与 return 等价 return后面的值可以是一个表达式 例如 例8 2中的函数max可以改写如下 max intx inty return x y x y 这样的函数体更为简短 只用一个return语句就把求值和返回都解决了 2 函数值的类型 既然函数有返回值 这个值当然应属于某一个确定的类型 应当在定义函数时指定函数值的类型 例如 intmax floatx floaty 函数值为整型 charletter charc1 charc2 函数值为字符型 doublemin intx inty 函数值为双精度型 读者会问 例8 2中的函数定义并没有说明其类型 为什么 语言规定 凡不加类型说明的函数 一律自动按整型处理 例8 2中的max函数返回值为整型 因此可不必说明 在定义函数时对函数值说明的类型一般应该和return语句中的表达式类型一致 例如 例8 2中用隐含方式指定max函数值为整型 而变量 也被指定为整型 通过return语句把 的值作为max的函数值 由max带回主调函数 的类型与max函数的类型是一致的 是正确的 3 如果函数值的类型和return语句中表达式的值不一致 则以函数类型为准 对数值型数据 可以自动进行类型转换 即函数类型决定返回值的类型 例8 3返回值类型与函数类型不同 将例8 2稍作改动 注意是变量的类型改动 main floata b intc scanf f f a b c max a b printf axis d n c max floatx floaty float z为实型变量 x y x y return 运行情况如下 1 5 2 5 axis2函数max定义为整型 而return语句中的 为实型 二者不一致 按上述规定 先将 转换为整型 然后max x y 带回一个整型值2回主调函数main 如果将main函数中的c定义为实型 用 f格式符输出 也是输出2 000000 有时 可以利用这一特点进行类型转换 如在函数中进行实型运算 希望返回的是整型量 可让系统去自动完成类型转换 但这种做法往往使程序 不清晰 可读性降低 容易弄错 而且并不是所有的类型都能互相转换的 如实数与字符类型数据之间 因此建议初学者不要采用这种方法 而应做到使函数类型与return返回值的类型一致 4 如果被调用函数中没有return语句 并不带回一个确定的 用户所希望得到的函数值 但实际上 函数并不是不带回值 而只是不带回有用的值 带回的是一个不确定的值 例如 在例8 1程序中 尽管没有要求printstar和print message函数带回值 但是如果在程序中出现下面的语句也是合法的 inta b c a printstar b print message c printstar printf d d d n a b c 运行时除了得到和例8 1一样的结果外 还可以输出a b c的值 今为21 20 21 a b c的值不一定有实际意义 今printstar函数输出21个字符 返回值为21 print message输出20个字符 返回值为20 5 为了明确表示 不带回值 可以用 void 定义 无类型 或称 空类型 例如 例8 1中的定义可以改为voidprintstar voidprint message 这样 系统就保证不使函数带回任何值 即禁止在调用函数中使用被调用函数的返回值 如果已将printstar和print message函数定义为void类型 则下面的用法就是错误的 a printstar b print message 编译时会给出出错信息 为使程序减少出错 保证正确调用 凡不要求带回函数值的函数 一般应定义为void类型 许多 语言书的程序中都大量用到void类型函数 读者应对此有一定了解 8 4 1函数调用的一般形式函数调用的一般形式为函数名 实参表列 如果是调用无参函数 则 实参表列 可以没有 但括弧不能省略 见例8 1 如果实参表列包含多个实参 则各参数间用逗号隔开 实参与形参的个数应相等 类型应一致 实参与形参按顺序对应 一一传递数据 但应说明 如果实参表列包括多个实参 对实参求值的顺序并不是确定的 有的系统按自左至右顺序求实参的值 有的系统则按自右至左顺序 许多 版本 例如Turbo 和 是按自右而左的顺序求值 8 4函数的调用 例8 4main inti 2 p p f i i 函数调用 printf d p intf inta intb 函数定义 intc if a b c 1 elseif a b c 0 elsec 1 return c 在TurboC系统上运行的结果为 0如果按自左至右顺序求实参的值 则函数调用相当于f 2 3 程序运行应得结果为 1 若按自右至左顺序求实参的值 则它相当于f 3 3 程序运行结果为 0 读者可以在所用的计算机系统上试一下 以便知道它所处理的方法 由于存在上述情况 使程序通用性受到影响 因此应当避免这种容易引起不同理解的情况 如果本意是按自左而右顺序求实参的值 可以改写为 i k i p f k 如果本意是自右而左求实参的值 可改写为j i p f j j 这种情况在printf函数中也同样存在 如printf d d i i 也发生上述同样的问题 若i的原值为3 在TurboC上运行结果为4 3 请读者务必注意 应该避免这种容易混淆的用法 8 4 2函数调用的方式按函数在程序中出现的位置来分 可以有以下三种函数调用方式 1 函数语句把函数调用作为一个语句 如例8 1中的printstar 这时不要求函数带回值 只要求函数完成一定的操作 2 函数表达式函数出现在一个表达式中 这种表达式称为函数表达式 这时要求函数带回一个确定的值以参加表达式的运算 例如 c 2 max a b 函数max是表达式的一部分 它的值乘2再赋给c 3 函数参数函数调用作为一个函数的实参 例如 m max a max b c 其中max b c 是一次函数调用 它的值作为max另一次调用的实参 m的值是a b c三者最大的 又如 printf d max a b 也是把max a b 作为printf函数的一个参数 函数调用作为函数的参数 实质上也是函数表达式形式调用的一种 因为函数的参数本来就要求是表达式形式 8 4 3对被调用函数的声明和函数原型在一个函数中调用另一函数 即被调用函数 需要具备哪些条件呢 1 首先被调用的函数必须是已经存在的函数 是库函数或用户自己定义的函数 但光有这一条件还不够 2 如果使用库函数 一般还应该在本文件开头用 include命令将调用有关库函数时所需用到的信息 包含 到本文件中来 例如 前几章中已经用过的 include其中 studio h 是一个 头文件 在studio h文件中放了输入输出库函数所用到的一些宏定义信息 如果不包含 studio h 文件中的信息 就无法使用输入输出 库中的函数 同样 使用数学库中的函数 应该用 include h是头文件所用的后缀 标志头文件 headerfile 有关宏定义等概念请见第8章 3 如果使用用户自己定义的函数 而且该函数与调用它的函数 即主调函数 在同一个文件中 一般还应该在主调函数中对被调用的函数作声明 即向编译系统声明将要调用此函数 并将有关信息通知编译系统 声明 一词的原文是declaration 过去在许多书中译为 说明 近年来 愈来愈多的计算机专家提出应称为声明 作者也认为称为 声明 更确切 表意更清楚 例8 5对被调用的函数作声明 main floatadd floatx floaty 对被调用函数的声明 floata b c scanf f f a b c add a b printf sumis f c floatadd floatx floaty 函数首部 float 函数体 x y return 运行情况如下 3 6 6 5 sumis10 000000这是一个很简单的函数调用 函数add的作用是求两个实数之和 得到的函数值也是实型 请注意程序第2行 floatadd floatx floaty 是对被调用的add函数作声明 注意 对函数的 定义 和 声明 不是一回事 定义 是指对函数功能的确立 包括指定函数名 函数值类型 形参及其类型 函数体等 它是一个完整的 独立的函数单位 而 声明 的作用则是把函数的名字 函数类型以及形参的类型 个数和顺序通知编译系统 以便在调用该函数时系统按此进行对照检查 例如函数 名是否正确 实参与形参的类型和个数是否一致 从程序中可以看到对函数的声明与函数定义中的第1行 函数首部 基本上是相同的 因此可以简单地照写已定义的函数的首部 再加一个分号 就成为了对函数的 声明 其实 在函数声明中也可以不写形参名 而只写形参的类型 如 floatadd float float 在C语言中 把以上形式的函数声明称为函数原型 functionprototype 使用函数原型是NC的一个重要特点 它的作用主要是利用它在程序的编译阶段对调用函数的合法性进行全面检查 从例8 5中可以看到main函数的位置在add函数的前面 而在进行如果 没有对函数的声明 当编译到包含函数调用的语句 c add a b 时 编译系统不知道add是不是函数名 也无法判断实参 a和b 的类型和个数是否正确 因而无法进行正确性的检查 只有在运行时才会发现实参与形参的类型或个数不一致 出现运行错误 但是在运行阶段发现错误并重新调试程序 是比较麻烦的 工作量也较大 应当在编译阶段尽可能多地发现错误 随之纠正错误 现在我们在函数调用之前用函数原型做了函数声明 因此编译系统记下了所需调用的函数的有关信息 在对 c add a b 进行编译时就 有章可循 了 编译系统根据函数的原型对函数的调用的编译时是从上到下逐行进行的 合法性进行全 面的检查 和函数原型不匹配的函数调用会导致编译出错 它属于语法错误 用户根据屏幕显示的出错信息很容易发现和纠正错误 函数原型的一般形式为 1 函数类型函数名 参数类型1 参数类型2 2 函数类型函数名 参数类型1 参数名1 参数类型2 参数名2 第 1 种形式是基本的形式 为了便于阅读程序 也允许在函数原型中加上参数名 就成了第 2 种形式 但编译系统不检查参数名 因此参数名是什么都无所谓 上面程序中的声明也可以写成 floatadd floata floatb 参数名不用x y 而用a b 效果完全相同 应当保证函数原型与函数首部写法上的一致 即函数类型 函数名 参数个数 参数类型和参数顺序必须相同 函数调用时函数名 实参个数应与函数原型一致 实参类型必须与函数原型中的形参类型赋值兼容 按第2章介绍的赋值规则进行类型转换 如果不是赋值兼容 就按出错处理 说明 1 以前的C版本的函数声明方式不是采用函数原型 而只声明函数名和函数类型 例如在例8 5中也可以采用下面的函数声明形式floatadd 不包括参数类型和参数个数 系统不检查参数类型和参数个数 新版本也兼容这种用法 但不提倡这种用法 因为它未进行全面的检查 2 实际上 如果在函数调用之前 没有对函数作声明 则编译系统会把笫一次遇到的该函数形式 函数定义或函数调用 作为函数的声明 并将函数类型默认为int型 例如例8 2在调用max函数 之前没有进行函数声明 编译时首先遇到的函数形式是函数调用 max a b 由于对原型的处理是不考虑参数名的 因此系统将max 加上int作为的函数声明 即intmax 因此 不少C教材说 如果函数类型为整型 可以在函数调用前不必作函数声明 但是使用这种方法时 系统无法对参数的类型做检查 若调用函数时参数使用不当 在编译时也不会报错 因此 为了程序清晰和安全 建议都加以声明为好 例如在例8 2中最好加上以下函数声明 intmax int int 或intmax intx inty 3 如果被调用函数的定义出现在主调函数之前 可以不必加以声明 因为编译系统已经先知道了已定义的函数类型 会根据函数首部提供的信息对函数的调用作正确性检查 如果把例8 5改写如下 即把main函数放在add函数的下面 就不必在main函数中对add声明 floatadd floatx floaty float x y return main 不必对add函数作声明 floata b c scanf f f a b c add a b printf f c 4 如果已在所有函数定义之前 在函数的外部已做了函数声明 则在各个主调函数中不必对所调用的函数再作声明 例如 charletter char char 以下3行在所有函数之前 且在函数外部 floatf float float inti float float main 不必声明它所调用的函数 charletter charc1 charc2 定义letter函数 floatf floatx floaty 定义f函数 inti float floatk 定义i函数 除了以上 2 3 4 所提到的三种情况外 都应该按上述介绍的方法对所调用函数作声明 否则编译时就会出现错误 用函数原型来声明函数 还能减少编写程序时可能出现的错误 由于函数声明的位置与函数调用语句的位置比较近 因此在写程序时便于就近参照函数原型来书写函数调用 不易出错 8 5函数的嵌套调用 语言的函数定义都是互相平行 独立的 也就是说在定义函数时 一个函数内不能包含另一个函数 这是和PASCAL不同的 PASCAL允许在定义一个函数时 其函数体内又包含另一个函数的完整定义 这就是嵌套定义 这个内嵌的函数只能被包含它的函数所调用 其他函数不能调用它 语句不能嵌套定义函数 但可以嵌套调用函数 也就是说 在调用一个函数的过程中 又调用另一个函数 见图8 5 图8 5 图8 5表示的是两层嵌套 连main函数共3层函数 其执行过程是 1 执行main函数的开头部分 2 遇函数调用a的操作语句 流程转去a函数 3 执行a函数的开头部分 4 遇调用b函数的操作语句 流程转去函数b 5 执行b函数 如果再无其他嵌套的函数 则完成b函数的全部操作 6 返回调用b函数处 即返回a函数 7 继续执行a函数中尚未执行的部分 直到a函数结束 8 返回main函数中调用a函数处 9 继续执行main函数的剩余部分直到结束 例8 6用弦截法求方程x3 5x2 16x 80 0的根 方法如下 1 取两个不同点x1 x2 如果f x1 和f x2 符号相反 则 x1 x2 区间内必有一个根 如果f x1 与f x2 同符号 则应改变x1 x2 直到f x1 f x2 异号为止 注意x1 x2的值不应差太大 以保证 x1 x2 区间内只有一个根 2 连接f x1 和f x2 两点 此线 即弦 交x轴于x 见图8 6 x点坐标可用下式求出 x x1 f x2 x2 f x1 f x2 f x1 再从x求出f x 3 若f x 与f x1 同符号 则根必在 x x2 区间内 此时将x作为新的x1 如果f x 与f x2 同符号 则表示根在 x1 x 区间内 将x作为新的x2 图8 6 图8 7 4 重复步骤 2 和 3 直到 f x 为止 为一个很小的数 例如10 6 此时认为f x 0 根据上述思路画出N S流程图 见图8 7 分别用几个函数来实现各部分功能 1 用函数f x 来求x的函数 x3 5x2 16x 80 2 用函数xpoint x1 x2 来求f x1 和f x2 的连线与x轴的交点x的坐标 3 用函数root x1 x2 来求 x1 x2 区间的那个实根 显然 执行root函数过程中要用到函数xpoint 而执行xpoint函数过程中要用到f函数 请读者先分析下面的程序 includefloatf floatx 定义f函数 以实现f x x3 5x2 16x 80 floaty y x 5 0 x 16 0 x 80 0 return y floatxpoint floatx1 floatx2 定义xpoint函数 求出弦与x轴交点 floaty y x1 f x2 x2 f x1 f x2 f x1 return y floatroot floatx1 floatx2 定义root函数 求近似根 inti floatx y y1 y1 f x1 do x xpoint x1 x2 y f x if y y1 0 f x 与f x1 同符号 y1 y x1 x elsex2 x while fabs y 0 0001 return x main 主函数 floatx1 x2 f1 f2 x do printf inputx1 x2 n scanf f f x1 x2 f1 f x1 f2 f x2 while f1 f2 0 x root x1 x2 printf rootofequationis 8 4f x 运行情况如下 inputx1 x2 2 6 rootofequationis5 0000 从程序可以看到 1 在定义函数时 函数名为f xpoint root的3个函数是互相独立的 并不互相从属 这3个函数均定为实型 2 3个函数的定义均出现在main函数之前 因此在main函数中不必对这3个函数作类型说明 3 程序从main函数开始执行 先执行一个do while循环 作用是 输入x1和x2 判别f x1 和f x2 是否异号 如果不是异号则重新输入x1和x2 直到满足f x1 与f x2 异号为止 然后用函数调用root x1 x2 求根x 调用root函数过程中 要调用xpoint函数来求f x1 与fx2 连线的交点x 在调用xpoint函数过程中要用到函数f来求x1和x2的相应的函数值f x1 和f x2 这就是函数的嵌套调用 见图8 8 图8 8 4 在root函数中要用到求绝对值的函数fabs 它是对实型数求绝对值的标准函数 它属于数学函数库 故在文件开头用 include即把使用数学库函数时所需用到的有关信息包含进来 8 6函数的递归调用在调用一个函数的过程中又出现直接或间接地调用该函数本身 称为函数的递归调用 语言的特点之一就在于允许函数的递归调用 例如 intf intx inty f y return 2 在调用函数f的过程中 又要调用f函数 这是直接调用本函数 见图8 9 下面是间接调用本函数 图8 9图8 10在调用f1函数过程中要调用f2函数 而在调用f2函数过程中又要调用f1函数 见图8 10 从图上可以看到 这两种递归调用都是无终止的自身调用 显然 程序中不应出现这种无终止的递归调用 而只应出现有限次数的 有终止的递归调用 这可以用if语句来控制 只有在某一条件成立时才继续执行递归调用 否则就不再继续 关于递归的概念 有些初学者感到不好理解 下面用一个通俗的例子来说明 例8 7有5个人坐在一起 问第5个人多少岁 他说比第4个人大2岁 问第4个人岁数 他说比第3个人大2岁 问第3个人 又说比第2个人大2岁 问第2个人 说比第1个人大2岁 最后问第1个人 他说是10岁 请问第5个人多大 显然 这是一个递归问题 要求第5个人的年龄 就必须先知道第4个人的年龄 而第4个人的年龄也不知道 要求第4个人的年龄必须先知道第3个人的年龄 而第3个人的年龄又取决于第2个人的年龄 第2个人的年龄取决于第1个人的年龄 而且每一个人的年龄都比其前1个人的年龄大2 即age 5 age 4 2age 4 age 3 2age 3 age 2 2age 2 age 1 2age 1 10可以用式子表述如下 age n 10 n 1 age n 1 2 n 1 可以看到 当n 1时 求第n个人的年龄的公式是相同的 因此可以用一个函数表示上述关系 图8 11表示求第5个人年龄的过程 图8 11 从图可知 求解可分成两个阶段 第一阶段是 回推 即将第n个人的年龄表示为第 n 1 个人年龄的函数 而第 n 1 个人的年龄仍然不知道 还要 回推 到第 n 2 个人的年龄 直到第1个人年龄 此时age 1 已知 不必再向前推了 然后开始第二阶段 采用递推方法 从第1个人的已知年龄推算出第2个人的年龄 12岁 从第2个人的年龄推算出第3个人的年龄 14岁 一直推算出第5个人的年龄 18岁 为止 也就是说 一个递归的问题可以分为 回推 和 递推 两个阶段 要经历许多步才能求出最后的值 显而易见 如果要求递归过程不是无限制进行下去 必须具有一个结束递归过程的条件 例如 age 1 10 就是使递归结束的条件 可以用一个函数来描述上述递归过程 age intn 求年龄的递归函数 intc c用作存放函数的返回值的变量 if n 1 c 10 elsec age n 1 2 return c main printf d age 5 运行结果如下 18main函数中只有一个语句 整个问题的求解全靠一个age 5 函数调用来解决 函数调用过程如图8 12所示 图8 12 从图8 12可以看到 age函数共被调用5次 即age 5 age 4 age 3 age 2 age 1 其中age 5 是main函数调用的 其余4次是在age函数中调用的 即递归调用4次 请读者仔细分析调用的过程 应当强调说明的是在某一次调用age函数时并不是立即得到age n 的值 而是一次又一次地进行递归调用 到age 1 时才有确定的值 然后再递推出age 2 age 3 age 4 age 5 请读者将程序和图8 11 图8 12结合起来认真分析 例8 8用递归方法求n 求n 可以用递推方法 即从1开始 乘2 再乘3 一直乘到n 这种方法容易理解 也容易实现 递推法的特点是从一个已知的事实出发 按一定规律推出下一个事实 再从这个新的已知的事实出发 再向下推出一个新的事实 这是和递归不同的 求n 也可以用递归方法 即5 等于4 5 而4 3 4 1 1 可用下面的递归公式表示 n 1 n 0 1 n n 1 n 1 有了例8 7的基础 很容易写出本题的程序 floatfac intn floatf if n 0 printf n 0 dataerror f 1 elseif n 0 n 1 f 1 elsef fac n 1 n return f main intn floaty printf inputaintegernumber scanf d n y fac n printf d 15 0f n y 运行情况如下 inputaintegernumber 10 10 3628800 例8 9hanoi 汉诺 塔问题 这是一个古典的数学问题 是一个只有用递归方法 而不可能用其他方法 解决的问题 问题是这样的 古代有一个梵塔 塔内有3个座A B C 开始时 座上有64个盘子 盘子大小不等 大的在下 小的在上 图8 13 有一个老和尚想把这64个盘子从 座移到 座 但每次只允许移动一个盘 且在移动过讨性 个座上都始终保持大盘在下 小盘在上 在移动过程中可以利用 座 要求编程序打印出移动的步骤 图8 13可以肯定地说 任何一个人 包括 天才 都不可能直接写出移动盘子的每一个具体步骤 请读者试验一下按上面的规律将5个盘子从A座移到C座 能否直接写出每一步骤 老和尚自然会这样想 假如有另外一个和尚能有办法将63个盘子从一个座移到另一座 那么 问题就解决了 此时老和尚只需这样做 1 命令第2个和尚将63个盘子从A座移到B座 2 自己将1个盘子 最底下的 最大的盘子 从A座移到C座 3 再命令第2个和尚将63个盘子从B座移到C座 至此 全部任务完成了 这就是递归方法 但是 有一个问题实际上未解决 第2个和尚怎样才能将63个盘子从A座移到B座 为了解决将63个盘子从A座移到B座 第2个和尚又想 如果有人能将62个盘子从一个座移到另一座 我就能将63个盘子从A座移到B座 他是这样做的 1 命令第3个和尚将62个盘子从A座移到C座 2 自己将1个盘子从A座移到B座 3 再命令第3