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