7 函数

本章内容

简单函数简介
使用 main
理解递归

我们已经见过 C 为条件执行提供的不同手段：程序根据某个值，选择一条分支而不是另一条分支继续执行。之所以可能“跳转”到程序代码的另一部分（例如 else 分支），是因为运行时根据运行时数据作出了决定。本章先讨论将控制无条件转移到代码其他部分的方式：这些方式本身不依赖任何运行时数据来决定去向。

此前见过的代码示例常常使用 C 库函数来提供我们不想（或无法）自行实现的功能，例如用 printf 打印，用 strlen 计算字符串长度。函数这一概念背后的想法是：把某项功能一次实现完毕，之后便可在其余代码中依赖这项功能。

我们已经见过好几个 main 函数的定义；它是程序开始执行的入口。本章将说明如何自行编写函数，让它们像 C 库函数一样提供功能。

引入函数概念，主要是为了实现模块化和代码因式分解：

函数避免代码重复。尤其是，它们可以避免极易引入的复制粘贴错误；修改一项功能时，也不必在多处重复编辑。因此，函数提高了可读性和可维护性。
使用函数可以缩短编译时间。封装在函数中的一段代码只需编译一次，而不必在每个使用位置各编译一次。
函数有利于日后复用代码。一旦我们把代码提取成提供某项功能的函数，就很容易把它应用到实现该函数时甚至未曾想到的其他场合。
函数提供清晰的接口。函数实参和返回类型清楚地规定了流入、流出某项计算的数据来自何处、属于什么类型。此外，函数还让我们能够规定计算的不变条件，即前置条件和后置条件。
对于需要使用一“栈”中间值的算法，函数提供了一种自然的表述方式。

除函数外，C 还有其他无条件转移控制的手段。它们大多用于处理错误状况，或正常控制流之外的异常情形：

exit、_Exit、quick_exit 和 abort 终止程序执行（见 8.8 节）。
goto 在函数体内部转移控制（见 13.2.2 节和 15.6 节）。
setjmp 和 longjmp 可用于无条件返回某个调用上下文（见 19.5 节）。
执行环境中的某些事件或对 raise 函数的调用可能引发信号，将控制交给专门的函数，即信号处理函数。

7.1 简单函数

我们已经使用过许多函数，也见过一些函数声明（例如 6.1.5 节）和函数定义（例如清单 6.3）。在所有这些函数中，圆括号 () 都承担着重要的语法作用。在函数声明和定义中，圆括号包围形参声明列表；在函数调用中，圆括号则容纳该次具体调用的实参列表。这一语法作用类似于数组所用的 []：在声明和定义中，它们包含相应维度的大小；在 A[i] 这样的访问中，它们用来指出所访问元素在数组中的位置。

到目前为止，我们见过的所有函数都有原型（prototype）：其声明和定义包含形参类型列表以及返回类型。回看清单 6.3 中的 leapyear 函数便可看清这一点：

bool leapyear(unsigned year) {
    /* 所有能被 4 整除的年份都是闰年，
       但世纪开端的年份除外；如果它又能被
       400 整除，则仍是闰年。 */
    return !(year % 4) && ((year % 100) || !(year % 400));
}

该函数的声明（不含定义）可以写成：

bool leapyear(unsigned year);

也可以省略形参名，并且／或者加上存储类说明符 extern：^[1]

extern bool leapyear(unsigned);

这类声明的要点是让编译器看见各实参的类型以及返回类型；此处的函数原型就是“接收一个 unsigned 并返回一个 bool 的函数”。

关键字 void 有两种特殊用法：

如果调用函数时不接收任何形参，就用关键字 void 代替形参列表，如最初的示例（清单 1.1）中的 main。
如果函数不返回值，就把返回类型写成 void，例如 swap_double。

函数原型可以在调用函数的地方帮助编译器。编译器只需知道该函数期望哪些形参。请看：

extern double fbar(double);

// ...
double fbar2 = fbar(2) / 2;

这里的调用 fbar(2) 与函数 fbar 的要求并不直接相容：它需要一个 double，收到的却是一个 signed int。不过，由于调用代码知道这一点，它可以先把 signed int 实参 2 转换为 double 值 2.0，再调用函数。在表达式中使用返回值时也是如此：调用方知道返回类型是 double，所以会对结果表达式施行浮点除法。

历史上，C 曾允许声明没有原型的函数；C23 已废除这种做法。

要点 7.1 #1

所有函数都必须有原型。

上述规则有一个显著的例外：有些函数可以接收数量不定的形参，例如 printf。它们采用一种称为可变参数列表（variable argument list）的形参处理机制，该机制由头文件 <stdarg.h> 提供。

我们稍后会看到其工作方式（17.4.2 节），但无论如何都应避免这种特性。仅凭使用 printf 的经验，你就能想象这种接口为何棘手：作为调用代码的程序员，你必须提供正确的 "%XX" 格式说明符，自行保证二者一致。

实现函数时，对所有返回类型不是 void 的函数，都必须注意提供返回值。一个函数中可以有多条 return 语句。

要点 7.1 #2

函数只有一个入口，却可以有多个返回点。

函数中的所有返回都必须与函数声明一致。对于应当返回值的函数，每条 return 语句都必须包含表达式；对于不应返回值的函数，return 语句包含表达式则是错误的。

要点 7.1 #3

函数的返回必须与其类型一致。

不过，调用方形参所遵循的同一规则也适用于返回值。如果某个值的类型可以转换为预期的返回类型，就会在返回发生之前完成转换。

如果函数类型是 void，甚至可以省略不带表达式的 return。

要点 7.1 #4

到达函数体末尾，等价于执行一条不带表达式的 return 语句。

与读取未初始化对象类似，一个应当返回值的函数如果未返回值，就会返回未初始化的值；如果调用处试图求取该值，就可能危及程序执行。因此，这种构造只允许用于不返回值的函数。

要点 7.1 #5

只有 void 函数才允许执行到函数体末尾。

7.2 `main` 很特殊

你也许已经注意到 main 的一些特殊之处。它作为程序入口，地位非常特殊：其原型由 C 标准强制规定，实现却由程序员提供。作为运行时系统与应用程序之间的枢纽，main 必须遵守一些特殊规则。

首先，为适应不同需求，它有若干种原型，程序必须实现其中一种。以下两种形式应当始终可用：

int main(void);
int main(int argc, char *argv[argc + 1]);

此外，各个 C 平台还可以提供其他接口。下面两种变体比较常见：

在某些嵌入式平台上，main 不需要返回运行时系统，此时返回类型可以是 void。
在许多平台上，第三个形参可以提供对“环境”的访问。

你不应依赖这些其他形式的存在。如果想编写可移植代码（你当然想），请坚持使用上面两种“官方”形式。对这两种形式而言，int 返回值向运行时系统表明程序执行是否成功：从程序员角度看，EXIT_SUCCESS 或 EXIT_FAILURE 分别表示执行成功或失败。只有这两个值能保证在所有平台上有效。

要点 7.2 #1

把 EXIT_SUCCESS 和 EXIT_FAILURE 用作 main 的返回值。

此外，main 还有一项特殊例外：它不要求显式写出 return 语句。

要点 7.2 #2

执行到 main 末尾，等价于以 EXIT_SUCCESS 执行 return。

我个人不太喜欢这种没有实质收益的例外；它只会让关于程序的论证变得更复杂。

库函数 exit 与 main 具有特殊关系。顾名思义，调用 exit 会终止程序。其原型如下：

[[noreturn]] void exit(int status);

这个函数终止程序的效果，与从 main 返回完全相同。形参 status 承担的角色，正是 main 中返回表达式所承担的角色。

要点 7.2 #3

调用 exit(s)，等价于在 main 中求取 return s。

我们还可以看到，exit 的原型很特殊，因为它的类型是 void。与 return 语句一样，exit 从不失败。

要点 7.2 #4

exit 从不失败，也绝不会返回调用方。

后一点由属性 [[noreturn]] 表明。这个属性只应当用于此类特殊函数。^[2]

main 的第二种原型还有另一项特性：argv，即命令行实参向量。我们见过一些示例，它们用这个向量把值从命令行传给程序。例如，在清单 3.1 中：

double const a = strtod(argv[i], nullptr); // 实参 -> double

这些命令行实参被解释为程序所用的 double 数据：

text

argv
 [0]          [1]          ...       [argc]
 char*        char*                  char*
   |            |                      |
   v            v                      v
"./heron"    "0.785"       ...         X

因此，对于 $i = 0, \dots, a r g c$ ，每个 argv[i] 都是一个指针，与我们此前遇到的指针类似。作为便于入门的近似理解，可以把它们看作字符串。

要点 7.2 #5

所有命令行实参都以字符串形式传递。

如何解释这些字符串取决于我们自己。在这个示例中，我们选择 strtod 函数来解码字符串中存储的 double 值。

argv 的各字符串中，有两个元素保存特殊值。

要点 7.2 #6

argv[0] 指向程序调用时所用的名称。

标准没有严格规定这个程序名应当是什么，但它通常是程序可执行文件的名称。

要点 7.2 #7

argv[argc] 是空指针。

利用这一性质，总能在 argv 数组中识别最后一个实参；不过这个特性没有多大用处，因为我们已经可以用 argc 处理该数组。

7.3 递归

函数的一项重要特性是封装。局部对象只在函数尚未退出时可见且存活；退出既可以由显式 return 引起，也可以因为执行越过函数体最外层的右花括号。它们的标识符（名称）不会与其他函数中的类似标识符冲突；一旦离开函数，留下的残局都会清理干净。

更妙的是，每次调用函数时，即使此前已经调用过它，也会创建一组新的局部对象（包括函数形参），并重新初始化。即使调用层级中已有一次对同一函数的调用仍处于活动状态，重新调用该函数时也是如此。直接或间接调用自身的函数称为递归函数，这一概念称为递归。

递归函数对于理解 C 函数至关重要。它们展示并运用了函数调用模型的主要特性；只有具备这些特性，递归函数才能充分发挥作用。作为第一个示例，我们来看欧几里得算法的一种实现，用它计算两个数的最大公约数（greatest common divisor，gcd）：

inline size_t gcd2(size_t a, size_t b) [[__unsequenced__]] {
    assert(a <= b);
    if (!a) return b;
    size_t r = b % a;
    return gcd2(r, a);
}

可以看到，这个函数短小精悍；不过它对实参作了一些假设，所以还算不上完整的 gcd 接口。^[3] 要理解其工作方式，我们必须透彻理解函数如何工作，以及如何把数学命题转换为算法。

给定两个整数 $a, b > 0$ ，最大公约数定义为同时整除 $a$ 和 $b$ 的最大整数 $c > 0$ ：

gcd (a, b) = max {c \in N ∣ c ∣ a 且 c ∣ b}

如果你不习惯这种数学表述，它可能有点难以下咽；不过，接下来的解释和示例会让这个概念清楚得多。

如果进一步假设 $a < b$ ，可以证明下面两个递归公式成立：

\begin{matrix} (2) & gcd (a, b) = gcd (a, b - a) \end{matrix}

\begin{matrix} (3) & gcd (a, b) = gcd (a, b mod a) \end{matrix}

也就是说，减去较小的整数，或者用较大整数除以较小整数所得的余数替换较大整数，都不会改变最大公约数。自古希腊数学时代起，人们就一直用这些公式计算最大公约数。它们通常归功于欧几里得（Εὐκλείδης，约公元前 300 年），但也可能早在他之前便已为人所知。此类公式（以及由此衍生的函数）之所以称为递归，是因为某一项的值（这里是 $gcd (a, b)$ ）借助同一项在不同值下的结果来说明（例如 $gcd (a, b - a)$ ）。

我们的 C 函数 gcd2 使用公式（3）。首先，第 9 行检查执行该函数的一项前置条件是否满足，即第一个实参是否小于或等于第二个实参。它使用 <assert.h> 中的 assert 宏完成检查。如果调用函数时给出的实参不满足该条件，程序便会中止并显示说明性消息（8.8 节将进一步解释 assert）。

要点 7.3 #1

明确写出函数的所有前置条件。

接着，第 10 行检查 a 是否为 0；如果是，就返回 b。这是递归算法中的关键一步。

要点 7.3 #2

在递归函数中，首先检查终止条件。

缺少终止检查会导致无限递归：函数不断调用自身的新副本，直至耗尽全部系统资源，程序随之崩溃。在拥有大量内存的现代系统上，这个过程可能会持续一阵子，而在此期间系统会完全失去响应。你最好不要尝试。

否则，我们计算 b 模 a 所得的余数 r（第 11 行），再以 r 和 a 递归调用函数，并直接返回该次调用的返回值。

图 7.1 展示了初始调用 gcd2(18, 30) 发出的各次递归调用。这里的递归深入四层，每一层都有自己的 a、b 和 r 副本。

text

调用层 0                 调用层 1                 调用层 2                 调用层 3
a = 18                   a = 12                   a = 6                    a = 0
b = 30                   b = 18                   b = 12                   b = 6
!a => false              !a => false              !a => false              !a => true
r = 12                   r = 6                    r = 0                         <= 6
gcd2(12, 18) =>          gcd2(6, 12) =>           gcd2(0, 6) =>
       <= 6                     <= 6                      <= 6

最终返回 6

图 7.1：递归调用 gcd2(18, 30)

对每次递归调用，模运算（要点 4.2.2 #5）都能保证自动满足前置条件。初次调用则必须由我们自行保证。最好的做法是使用另一个函数，也就是包装函数（wrapper）：

inline size_t gcd(size_t a, size_t b) [[__unsequenced__]] {
    assert(a);
    assert(b);
    if (a < b)
        return gcd2(a, b);
    else
        return gcd2(b, a);
}

要点 7.3 #3

在包装函数中保证递归函数的前置条件。

这样就无须在每次递归调用时检查前置条件：assert 宏可以在最终的生产对象文件中禁用。

另一个著名的递归整数序列是斐波那契数列；早在公元前 200 年左右的印度文献中就已经出现了这组数。用现代形式可以把它定义为：

\begin{matrix} (4) & F_{1} = 1 \end{matrix}

\begin{matrix} (5) & F_{2} = 1 \end{matrix}

\begin{matrix} (6) & F_{i} = F_{i - 1} + F_{i - 2} 对所有 i > 2 \end{matrix}

斐波那契数列增长很快。最初的一些元素是 1、1、2、3、5、8、13、21、34、55、89、144、377、610 和 987。

利用黄金比例

\begin{matrix} (7) & φ = \frac{1 + \sqrt{5}}{2} = 1.61803 \dots \end{matrix}

可以证明

\begin{matrix} (8) & F_{n} = \frac{φ^{n} - (- φ)^{- n}}{\sqrt{5}} \end{matrix}

因此在渐近意义下有

\begin{matrix} (9) & F_{n} \approx \frac{φ^{n}}{\sqrt{5}} \end{matrix}

所以 $F_{n}$ 呈指数增长。

递归的数学定义可以直接翻译成 C 函数：

size_t fib(size_t n) [[__unsequenced__]] {
    if (n < 3)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}

这里仍然首先检查终止条件，即调用实参 n 是否小于 3。如果是，返回值为 1；否则，返回以 n-1 和 n-2 为实参的两次调用之和。

图 7.2 展示了一次实参值很小的 fib 调用。可以看到，这会形成三层相互叠置的调用：它们调用同一函数，却使用不同的实参。由于公式（6）用到数列中的两个不同值，这里的递归调用结构比 gcd2 复杂得多。尤其是其中有三次叶调用：这些函数调用满足终止条件，因而自身不再递归。[练习 55]

text

调用层 0：n = 4，n < 3 => false
|
+-- 调用层 1：fib(3)，n = 3，n < 3 => false
|   |
|   +-- 调用层 2：fib(2)，n = 2，n < 3 => true，返回 1
|   |
|   +-- 调用层 2：fib(1)，n = 1，n < 3 => true，返回 1
|   |
|   `-- 返回 1 + 1 = 2
|
+-- 调用层 1：fib(2)，n = 2，n < 3 => true，返回 1
|
`-- 返回 2 + 1 = 3

图 7.2：递归调用 fib(4)

按这种方式实现，斐波那契数的计算相当缓慢。[练习 56] 事实上，很容易看出，函数本身的递归公式也会为函数执行时间导出类似公式：

\begin{matrix} (10) & T_{fib} (1) = C_{0} \end{matrix}

\begin{matrix} (11) & T_{fib} (2) = C_{0} \end{matrix}

\begin{matrix} (12) & T_{fib} (i) = T_{fib} (i - 1) + T_{fib} (i - 2) + C_{1} 对所有 i > 3 \end{matrix}

其中 $C_{0}$ 和 $C_{1}$ 是取决于平台的常数。

练习 55

证明调用 fib(n) 会引发 $F_{n}$ 次叶调用。

练习 56

测量以不同值作为 n 调用 fib(n) 所需的时间。在 POSIX 系统上，可以用 /bin/time 测量程序执行的运行时间。

由此可知，无论平台如何、实现多么巧妙，函数执行时间始终具有如下形式：

\begin{matrix} (13) & T_{fib} (n) = F_{n} (C_{0} + C_{1}) \approx φ^{n} \cdot \frac{C_{0} + C_{1}}{\sqrt{5}} = φ^{n} \cdot C_{2} \end{matrix}

其中 $C_{2}$ 是另一个取决于平台的常数。因此，fib(n) 的执行时间相对于 n 呈指数增长，通常足以让这种函数在实际中无法使用。

要点 7.3 #4

多重递归可能导致执行时间呈指数增长。

观察图 7.2 中的嵌套调用可以发现，fib(2) 被调用了两次，计算 fib(2) 的全部工作因而重复了一遍。函数 fibCacheRec 避免了这种重复。它还接收一个实参 cache；这是一个数组，保存所有已经计算出的值：

/* 借助可能保存着先前计算结果的缓存，计算斐波那契数 n。 */
size_t fibCacheRec(size_t n, size_t cache[static n]) {
    if (!cache[n - 1]) {
        cache[n - 1]
            = fibCacheRec(n - 1, cache) + fibCacheRec(n - 2, cache);
    }
    return cache[n - 1];
}

size_t fibCache(size_t n) {
    if (n + 1 <= 3) return 1;
    /* 建立一个 VLA 来缓存各个值。 */
#if __STDC_VERSION__ > 202311L
    /* 从 C23 起，VLA 可以默认初始化。 */
    size_t cache[n] = { };
#else
    size_t cache[n]; memset(cache, 0, n * sizeof(*cache));
#endif
    /* 用赋值代替非平凡初始化。 */
    cache[0] = 1; cache[1] = 1;
    /* 调用递归函数。 */
    return fibCacheRec(n, cache);
}

我们用存储空间换取计算时间，只有某个值尚未计算时，才会发生相应的递归调用。因此，调用 fibCache(i) 的执行时间相对于 n 是线性的：

\begin{matrix} (14) & T_{fibCache} (n) = n \cdot C_{3} \end{matrix}

其中 $C_{3}$ 是取决于平台的参数。[练习 57] 仅仅改变实现数列的算法，就能把执行时间从指数级降至线性级！我们既没有（也不需要）讨论实现细节，也没有实际测量执行时间。[练习 58]

要点 7.3 #5

糟糕的算法绝不会带来高性能实现。

要点 7.3 #6

改进算法可以显著提升性能。

练习 57

证明公式（14）。

练习 58

使用与 fib 相同的各个值调用 fibCache(n)，并测量所需时间。

有趣的是，fib2Rec 展示了斐波那契数列的第三种实现算法。它不使用变长数组（VLA），而只使用固定长度数组（CLA）：

void fib2rec(size_t n, size_t buf[static 2]) [[__unsequenced__]]
{
    if (n > 2) {
        size_t res = buf[0] + buf[1];
        buf[1] = buf[0];
        buf[0] = res;
        fib2rec(n - 1, buf);
    }
}

size_t fib2(size_t n) [[__unsequenced__]] {
    size_t res[2] = { 1, 1, };
    fib2rec(n, res);
    return res[0];
}

证明这个版本依然正确，留作练习。[练习 59] 此外，到目前为止，我们只有一些很初步的工具，还无法充分判断它在任何有意义的”更快”标准下是否确实更快。[练习 60]

挑战 9：因数分解

现在我们已经讲完函数，请尝试实现一个程序 factor：它从命令行接收一个数 $N$ ，并输出

text

N: F0 F1 F2 ...

其中 $F_{0}$ 等是 $N$ 的所有素因数。

实现的核心应当是一个函数：给定一个 size_t 类型的值，返回其最小素因数。

扩展这个程序，让它能够接收一列这样的数，并为每个数输出一行。

练习 59

使用迭代语句，把 fib2rec 转换为非递归函数 fib2iter。

练习 60

使用与 fib 相同的各个值调用 fib2(n)，并测量所需时间。

小结

函数具有原型，原型决定函数可以怎样调用。
终止 main 与调用 exit 效果相同。
每次函数调用都有自己的一份局部对象副本，函数可以递归调用。

关于关键字 extern 的更多细节，将在 13.2 节介绍。 ↩︎
C23 以前的 C 版本使用关键字 _Noreturn，并在头文件 <stdnoreturn.h> 中提供其便于排印的宏形式 noreturn。 ↩︎
[[unsequenced]] 属性要到很后面的 16.3 节才会讨论。 ↩︎

7 函数 ​

7.1 简单函数 ​

7.2 main 很特殊 ​

7.3 递归 ​

小结 ​

7 函数

7.1 简单函数

7.2 `main` 很特殊

7.3 递归

小结