# 13.10: Binary Numbers

- Page ID
- 18824

The `countdown`

example has three parts: (1) it checks the base case, (2) displays something, and (3) makes a recursive call. What do you think happens if you reverse steps 2 and 3, making the recursive call *before* displaying?

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

The stack diagram is the same as before, and the method is still called *n* times. But now the `System.out.println`

happens just before each recursive call returns. As a result, it counts up instead of down:

Blastoff! 1 2 3

This behavior comes in handy when it is easier to compute results in reverse order. For example, to convert a decimal integer into its **binary** representation, you repeatedly divide the number by two:

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

Reading these remainders from bottom to top, 23 in binary is 10111. For more background about binary numbers, see http://www.mathsisfun.com/binary-number-system.html.

Here is a recursive method that displays the binary representation of any positive integer:

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

If `value`

is zero, `displayBinary`

does nothing (that’s the base case). If the argument is positive, the method divides it by two and calls `displayBinary`

recursively. When the recursive call returns, the method displays one digit of the result and returns (again).

The leftmost digit is at the bottom of the stack, so it gets displayed first. The rightmost digit, at the top of the stack, gets displayed last. After invoking `displayBinary`

, we use `println`

to complete the output.

displayBinary(23); System.out.println(); // output is 10111

Learning to think recursively is an important aspect of learning to think like a computer scientist. Many algorithms can be written concisely with recursive methods that perform computations on the way down, on the way up, or both.