21-递归和倒序计算

9.3.4　递归和倒序计算

递归在处理倒序时非常方便（在解决这类问题中，递归比循环简单）。我们要解决的问题是：编写一个函数，打印一个整数的二进制数。二进制表示法根据2的幂来表示数字。例如，十进制数234实际上是2×10²+3×10¹+4×10⁰，所以二进制数101实际上是1×2²+0×2¹+1×2⁰。二进制数由0和1表示。

我们要设计一个以二进制形式表示整数的方法或算法（algorithm）。例如，如何用二进制表示十进制数5？在二进制中，奇数的末尾一定是1，偶数的末尾一定是0，所以通过 5 % 2 即可确定 5 的二进制数的最后一位是 1 还是 0 。一般而言，对于数字 n ，其二进制的最后一位是 n % 2 。因此，计算的第一位数字实际上是待输出二进制数的最后一位。这一规律提示我们，在递归函数的递归调用之前计算 n % 2 ，在递归调用之后打印计算结果。这样，计算的第 1 个值正好是最后一个打印的值。

要获得下一位数字，必须把原数除以 2 。这种计算方法相当于在十进制下把小数点左移一位，如果计算结果是偶数，那么二进制的下一位数就是 0 ；如果是奇数，就是 1 。例如， 5/2 得 2 （整数除法）， 2 是偶数（ 2%2 得 0 ），所以下一位二进制数是 0 。到目前为止，我们已经获得 01 。继续重复这个过程。 2/2 得 1 ， 1%2 得 1 ，所以下一位二进制数是 1 。因此，我们得到 5 的等价二进制数是 101 。那么，程序应该何时停止计算？当与 2 相除的结果小于 2 时停止计算，因为只要结果大于或等于 2 ，就说明还有二进制位。每次除以 2 就相当于去掉一位二进制，直到计算出最后一位为止（如果不好理解，可以拿十进制数来做类比： 628%10 得 8 ，因此 8 就是该数最后一位；而 628/10 得 62 ，而 62%10 得 2 ，所以该数的下一位是 2 ，以此类推）。程序清单9.8演示了上述算法。

程序清单9.8　 binary.c 程序

/* binary.c -- 以二进制形式打印制整数 */
#include <stdio.h>
void to_binary(unsigned long n);
int main(void)
{
     unsigned long number;
     printf("Enter an integer (q to quit):\n");
     while (scanf("%lu", &number) == 1)
     {
          printf("Binary equivalent: ");
          to_binary(number);
          putchar('\n');
          printf("Enter an integer (q to quit):\n");
     }
     printf("Done.\n");
     return 0;
}
void to_binary(unsigned long n)   /* 递归函数 */
{
     int r;
     r = n % 2;
     if (n >= 2)
          to_binary(n / 2);
     putchar(r == 0 ? '0' : '1');
     return;
}

在该程序中，如果 r 的值是 0 ， to_binary() 函数就显示字符 '0' ；如果 r 的值是 1 ， to_binary() 函数则显示字符 '1' 。条件表达式 r == 0 ? '0' : '1' 用于把数值转换成字符。

下面是该程序的运行示例：

Enter an integer (q to quit):
9
Binary equivalent: 1001
Enter an integer (q to quit):
255
Binary equivalent: 11111111
Enter an integer (q to quit):
1024
Binary equivalent: 10000000000
Enter an integer (q to quit):
q
Done.

不用递归，是否能实现这种用二进制形式表示整数的算法？当然可以。但是由于这种算法要首先计算最后一位二进制数，所以在显示结果之前必须把所有的位数都存储在别处（例如，数组）。第15章中会介绍一个不用递归实现该算法的例子。