5.10　二进制数

5.10　二进制数

前面的方法 countdown 由三部分组成：(1) 检查基线条件；(2) 显示输出；(3) 执行递归调用。如果将第 2 步和第 3 步的顺序调换一下，即先执行递归调用再显示输出，你认为结果将如何呢？

public static void countup(int n) {
    if (n == 0) {
        System.out.println("Blastoff!");
    } else {
        countup(n - 1);
        System.out.println(n);
    }
}

栈图与以前相同，并且这个方法也将被调用 n 次，但 System.out.println 将在递归调用返回前执行，因此结果是顺数而不是倒数：

Blastoff!
1
2
3

在按相反的顺序更容易计算结果时，可利用这种行为。例如，要想将十进制整数转换为用二进制（binary）表示，可反复地除以 2：

23 / 2 is 11 remainder 1
11 / 2 is  5 remainder 1
 5 / 2 is  2 remainder 1
 2 / 2 is  1 remainder 0
 1 / 2 is  0 remainder 1

从下往上阅读这些余数就可得到 23 的二进制表示——10111。要想了解更多有关二进制的详细信息，请参阅 http://www.mathsisfun.com/binary-number-system.html。

下面的递归方法可用于显示任何正整数的二进制表示：

public static void displayBinary(int value) {
    if (value > 0) {
        displayBinary(value / 2);
        System.out.print(value % 2);
    }
}

如果 value 为 0，displayBinary 就什么都不做（这就是基线条件）。如果传入的实参为正，该方法就将其除以 2，再递归地调用自己。这个方法在递归调用返回前显示结果中的一位。

最左边的那位位于栈底，因此最先显示；最右边的那位位于栈顶，因此最后显示。调用 displayBinary 后，我们可以用 println 指出输出到此结束：

displayBinary(23);
System.out.println();
// 输出为10111

要想像计算机科学家那样思考，学会递归思维很重要。向上或向下执行计算的递归算法可以用简洁的方式实现很多算法。

5.10 二进制数