2024年4月14日发(作者：)
C 递归
C语言中的函数可以递归调用，即函数可以直接或间接调用自身。我们考虑一下将一个数
作为字符串打印的情况。前面讲过，数字是以反序生成的：低位数字先于高位数字生成，但
它们必须以与此相反的次序打印。
解决该问题有两种方法。一种方法是将生成的各个数字依次存储到一个数组中，然后再
以相反的次序打印它们，这种方式与3.6 节中itoa函数的处理方式相似。另一种方法则是
使
用递归，函数printd 首先调用它自身打印前面的（高位）数字，然后再打印后面的数字。
这里编写的函数不能处理最大的负数。
#include
/* printd: print n in decimal */
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，然后再返回到第二次调用。从第三次调用返回后的第二次调用同样也将先打
印
2，然后再返回到第一次调用。返回到第一次调用时将打3，随之结束函数的执行。
另外一个能较好说明递归的例子是快速排序。快速排序算法是C. A. R. Hoare于1962 年发
明的。对于一个给定的数组，从中选择一个元素，以该元素为界将其余元素划分为两个子集，
一个子集中的所有元素都小于该元索，另一个子集中的所有元素都大于或等于该元素。对这
样两个子集递归执行这一过程，当某个子集中的元素数小于2 时，这个子集就不需要再次
排
序，终止递归。
从执行速度来讲，下列版本的快速排序函数可能不是最快的，但它是最简单的算法之一。
在每次划分子集时，该算法总是选取各个子数组的中间元素。
/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
swap(v, left, (left + right)/2); /* move partition elem */
last = left; /* to v[0] */
for (i = left + 1; i <= right; i++) /* partition */
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last); /* restore partition elem */
qsort(v, left, last-1);
qsort(v, last+1, right);
}
这里之所以将数组元素交换操作放在一个单独的函数swap 中，是因为它在qsort 函数中
要
使用3 次。
/* swap: interchange v[i] and 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)函数，以将字符串s倒置。
发布评论