Java Reference
In-Depth Information
5.3 Converting a Decimal Number to Binary Using Recursion
In Section 4.3.1, we used a stack to convert an integer from decimal to binary. We will now show how to write a
recursive function to perform the same task.
To see what needs to be done, suppose
n
is
13
, which is
1101
in binary. Recall that
n % 2
gives us the
last
bit of
the binary equivalent of
n
. If, somehow, we have a way to print all but the last bit, then we can print all but the last bit
followed by
n % 2
. But “printing all but the last bit” is the same as printing the binary equivalent of
n/2
.
For example,
1101
is
110
followed by
1
;
110
is the binary equivalent of
6
, which is
13/2
, and
1
is
13 % 2
. So, we can
print the binary equivalent of
n
as follows:
print binary of n / 2
print n % 2
We use the same method to print the binary equivalent of
6
. This is the binary equivalent of
6/2
=
3
, which is
11
,
followed by
6 % 2
, which is
0
; this gives
110
.
We use the same method to print the binary equivalent of
3
. This is the binary equivalent of
3/2
=
1
, which is
1
,
followed by
3 % 2
, which is
1
; this gives
11
.
We use the same method to print the binary equivalent of
1
. This is the binary equivalent of
1/2
=
0
followed
by
1 % 2
, which is
1
; if we “do nothing” for
0
, this will give us
1
.
We stop when we get to the stage where we need to find the binary equivalent of
0
. This leads us to the following
function:
public static void decToBin(int n) {
if (n > 0) {
decToBin(n / 2);
System.out.printf("%d", n % 2);
}
}
The call
decToBin(13)
will print
1101
.
Note how much more compact this is than Program P4.4. However, it is not more efficient. The stacking/
unstacking that is done explicitly in Program P4.4 is done here by the recursive mechanism provided by the language
when a function calls itself. To illustrate, let's trace the call
decToBin(13)
.
1.
On the first call, n assumes the value 13.
2.
While the call decToBin(13) is executing, the call decToBin(6) is made; 13 is pushed onto
the runtime stack, and n assumes the value 6.
3.
While the call decToBin(6) is executing, the call decToBin(3) is made; 6 is pushed onto the
stack, and n assumes the value 3.
4.
While the call decToBin(3) is executing, the call decToBin(1) is made; 3 is pushed onto the
stack, and n assumes the value 1.
5.
While the call decToBin(1) is executing, the call decToBin(0) is made; 1 is pushed onto the
stack, and n assumes the value 0.
6.
At this stage, the stack contains 13, 6, 3, 1.
7.
Since n is 0, this call of the function returns immediately; so far, nothing has been printed.
8.
When the call decToBin(0) returns, the argument on top of the stack, 1, is reinstated as the
value of n.
Search WWH ::
Custom Search