C语言K&R圣经笔记 4.10递归 4.11 C预处理

4.10 递归

C 函数可以被递归地使用，也就是说，函数可以直接或者间接地调用它自身。回顾一下将数值转换成字符串输出的问题。我们前面提到过，数位是以错误的顺序生成的：低数位比高数位先得到，但它们只能以相反的方式（先高后低）打印出来。

这个问题有两种解决方案。一个是在数位生成时把它们保存在数组里面，然后以倒序方式打印出来，这正是我们在 3.6节中 itoa 所采用的方案。另一种是递归方案，其中 printd 首先调用自身来处理所有之前的数位，然后打印末尾的数位。这个版本也和 3.6节 的一样，在处理最大的负数时有问题。

#include <stdio.h>

/* 以十进制格式输出n */
void printd(int n)
{
    if (n < 0) {
        putchar('-');
        n = -n;
    }
    if (n / 10)
        printd(n / 10);
    putchar(n % 10 + '0');
}

当函数递归调用自身时，每次调用都会获取一整套全新的自动变量，完全独立于前一套中所有的自动变量。因此，在printd(123) 中，第一个 printd 收到的参数?n = 123。它将 12 传给第二个 printd，后者将 1 传给第三个 printd。第三层的 printd 打印出1，然后返回到第二层。第二层的 printd 打印 2， 然后返回到第一层。第一层的 printd 打印 3 并结束。

还有个不错的递归样例：快速排序，这是1962年 C.A.R.Hoare 发明的排序算法。给出一个数组，选中其中一个元素，则数组的其他元素被划分成两个子集—— 比该元素小的子集，以及不小于该元素的的子集。同样的过程再递归地应用到两个子集上。当子集少于两个元素时，它就不用再排序了；此时递归停止。

我们这个版本的快速排序并不是最快的，但却是最简单版本的之一。我们使用每个子数组的中间元素来做划分。

/* qsort：把v[left]...v[right]按升序排列 */
void qsort(int v[], int left, int right)
{
    int i, last;
    void swap(int v[], int i, int j);

    if (left >= right)    /* 如果数组少于两个元素，则什么都不用做 */
        return;
    swap(v, left, (left+right)/2);    /* 用于划分的元素移动到v[0] */
    last = left;
    for (i = left+1; i <= right; i++)    /* 划分 */
        if (v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);        /* 恢复划分的元素 */
    qsort(v, left, last - 1);
    qsort(v, last + 1, right);
}

我们把交换操作移到一个独立的函数 swap 中，因为它在 qsort 中出现了三次。

/* swap：交换v[i]和v[j] */
void swap(int v[], int i, int j)
{
    int temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

标准库包含了一个能够对任何类型对象排序的?qsort 版本。

递归不一定能节省内存，因为当前正处理的数值栈必须在某处维护。递归也不会更快。但递归代码更加紧凑，而且相比等价的非递归代码，递归代码通常更容易编写和阅读。对于用递归方式定义的数据结构如树，递归也是特别方便的；我们会在6.5节看到一个很不错的例子。

练习4-12、参考 printd 的思路，写一个递归版本的 itoa，即通过递归调用将整数转换为字符串

练习4-13、写一个递归版本的函数 reverse(s)，在原处将字符串反转。

4.11 C预处理

C 语言的某些机制是以预处理的方式提供的，预处理从概念上来说，是在编译过程中单独的第一步。两个最常用的预处理特性分别是 #include，用于在编译期间包含一个文件的内容，以及 #define，用来将一个标识符替换成为任意的字符序列。本节描述的其他特性包括条件编译和带参数的宏。

4.11.1 文件包含

文件包含能使我们很容易地处理代码中大批的 #define 和声明。如下形式的代码行

#include "文件名"

或

#include <文件名>

会被替换成 文件名?所对应文件的内容。若文件名是用双引号""引起来的，通常会从源程序所在的目录开始查找文件；如果没找到，或者文件名是用尖括号<>括起来的，则以实现【即编译器】定义的规则来查找文件。被包含的文件本身也可以有 #include 行。

通常在源文件的开头会有几个 #include 行，用于包含公共的 #define 语句和 extern 声明，或者用于访问来自头文件如 <stdio.h> 的库函数原型。（严格地说，这些可以不是文件；头文件如何访问的细节是依赖于编译器实现的。）

对大程序来说，#include 是将许多声明捆绑在一起的首选方法。它保证给所有的源文件都提供相同的定义和变量声明，这样就能消除一种特别令人讨厌的bug。自然地，当被包含的文件修改了，所有依赖它的文件都必须重新编译。

4.11.2 宏替换

宏定义的形式如下

#define? 名字? 替换文本

这代表一种最简单类型的宏替换——后续出现的标识符?名字?都会被替换成 替换文本。在 #define 中，名字的格式与变量相同，而替换文本可以是任意格式。正常来说，替换文本是该行剩下的部分，但是一个长定义可能延续好几行，这可以通过在要接续的每行末尾加上一个反斜杠 \ 来做到 。用 #define 定义的名字，其作用域是从它所定义的点开始，直到所编译源文件的末尾结束。定义可以使用之前的定义。替换只会对标识符替换，而不会对双引号内的字符串替换。例如，假设定义过 一个名字 YES，则在 printf("YES") 和 YESMAN 中，都不会发生替换。

任何名字都可以用任意的替换文本来定义。例如

#define forever for(;;)    /* 无限循环 */

定义了一个新单词 forever，用作无限循环。

还可以定义带参数的宏，这样，不同的宏调用可以得到不同的替换文本。例如，定义一个叫做 max 的宏：

#define max(A, B)    ((A) > (B) ? (A) : (B))

尽管 max 看起来像是一个函数调用，但它在使用时会被扩展成内联（in-line）代码。每个出现的形参（这里是 A 或 B）都会被对应的实参替换。因此

x = max(p+q, r+s);

会被替换成

x = ((p+q) > (r+s) ? (p+q) : (r+s));

只要这两个参数的处理方式是一致的，这个宏就能用于任何数据类型；不同的数据类型，不需要写多个不同类型的 max 宏，但如果用函数来做的话，那就需要多个了。

如果你检查一下 max 的扩展形式，就会注意到一些缺陷。比如，表达式被求值了两次；如果涉及到副作用（side effect），如自增操作符或者输入输出，那就糟糕了。例如

max(i++, j++);    /* 错误 */

会把其中较大的值增加两次。另外，还要注意使用括号，来保证求值顺序；看看下面这个宏

#define square(x)   x * x     /* 错误 */

在调用 square(z+1)?时会发生什么。

然而，宏是有价值的。一个实际的例子来自 <stdio.h>，其中 getchar 和 putchar 通常定义成宏，以避免运行时在每个字符处理时都发起一次函数调用的开销。<ctype.h> 中的函数通常也是用宏实现的。

名字可以使用 #undef 来取消定义，这通常用来保证一个例程的确是一个函数而不是宏：

#undef getchar

int getchar(void) { ... }

?在双引号字符串内的形参是不会被替换的。然而，如果在替换文本中，形参以 # 开头，则这个组合（即 # 和形参）会被扩展成一个双引号字符串，其中的参数被替换为实参。例如，这个机制可以与字符串拼接的机制【即两个连续（或用空白字符分隔）的字符串常量如?"hello,"? "world" 会被编译器自动拼接为 "hello,world"】配合起来，写出一个调试打印的宏：

#define dprint(expr)  printf(#expr " = %g\n", expr)

例如，调用

 dprint(x/y);

则宏被扩展为

printf("x/y" " = %g\n", x/y);

字符串连接后，效果为

printf("x/y = %g\n", x/y);

在实参中，每个双引号 " 被替换为 \"，而每个反斜杠 \ 被替换为 \\，所以结果还是合法的字符串常量。【？？？】

预处理操作符 ## 用来在宏扩展过程中连接参数。如果替换文本中的参数与 ## 相连，则参数会被替换成实参，## 及其两边的空格会被删除，得到的结果会被再次扫描。例如，下面这个 macro 宏会连接它的两个参数：

#define paste(front, back)  front ## back

因此，paste(name, 1) 用来创建标识符 name1。

## 的嵌套使用规则晦涩难懂；进一步的细节参见附录A。

练习4-14、定义宏 swap(t, x, y) ，用来交换两个类型为 t 的参数。（块结构会有帮助）

4.11.3 条件包含

可以使用在预处理过程期间求值的条件语句，来控制预处理过程本身。这就提供了一种基于在编译期间求值的条件，来选择性地包含代码的方法。

#if 开头的行对一个整型常量表达式求值（不可以包含 sizeof，强制类型转换 和 enum 常量）。如果表达式结果非零，则后续的行都会被包含，直到遇到 #endif 、 #elif 或 #else 为止。（预处理语句 #elif 类似 else if。）在 #if 中可以使用表达式 defined(名称) ，如果 名称 被定义过，则值为1，否则为0。

例如，为了保证某个文件 hdr.h中的内容只被包含一次，会用一个条件把文件的内容包围起来，如下所示：

#if !defined(HDR)
#define HDR

/* hdr.h的内容在这里 */

#endif

对 hdr.h 的首次包含定义了名称 HDR；后续如果再包含，会发现这个名字已经被定义了，就直接跳到 #endif。类似的风格可以用于避免多次包含文件。如果能贯彻使用这个风格，则每个头文件都能包含它自身所依赖的所有其他头文件，而头文件的用户不需要去处理头文件相互间的依赖。

下面这个序列测试 SYSTEM 这个名称，来确定包含哪个头文件：

#if SYSTEM == SYSV
    #define HDR "sysv.h"
#elif SYSTEM == BSD
    #define HDR "bsd.h"
#elif SYSTEM == MSDOS
    #define HDR "msdos.h"
#else
    #define HDR "default.h"
#endif
#include HRD

#ifdef 和 #ifndef 是用来检查一个名字是否有被定义的特殊形式。第一个例子中的 #if 可以写成

#ifndef HDR
#define HDR

/* hdr.h的内容在这里 */

#endif

（第四章完）