RECURSION - Java Programming: From Problem Analysis to Program Design - page 889

problem. Of course, for problems such as mission control systems, efficiency is absolutely
critical and, therefore, the efficiency factor dictates the solution method.
As a general rule, if you think an iterative solution is more obvious and easier to understand
than a recursive solution, use the iterative solution, which is more efficient. On the other
hand, problems exist for which the recursive solution is more obvious or easier to construct,
such as the Tower of Hanoi problem. (In fact, it is difficult to construct an iterative solution
for the Tower of Hanoi problem.) Keeping in mind the power of recursion, if the definition
of a problem is inherently recursive, then you should consider a recursive solution.

PROGRAMMING EXAMPLE: Decimal to Binary Conversion
This programming example discusses and designs a program that uses recursion to
convert a nonnegative integer in decimal format—that is, base 10—into the equiva-
lent binary number—that is, base 2. First, we define some terms.
Let x be a nonnegative integer. We call the remainder of x after division by 2 the
rightmost bit of x .
Thus, the rightmost bit of 33 is 1 because 33 % 2 is 1 , and the rightmost bit of 28 is 0
because 28 % 2 is 0 .
We first use an example to illustrate the algorithm to convert an integer in base 10 to
the equivalent number in binary format.
Suppose we want to find the binary representation of 35 . First, we divide 35 by 2 .
The quotient is 17 and the remainder—that is, the rightmost bit of 35 —is 1 . Next,
we divide 17 by 2 . The quotient is 8 and the remainder—that is, the rightmost bit of
17 —is 1 . Next, we divide 8 by 2 . The quotient is 4 and the remainder—that is, the
rightmost bit of 8 —is 0 . We continue this process until the quotient becomes 0 .
The rightmost bit of 35 cannot be printed until we have printed the rightmost bit
of 17 . The rightmost bit of 17 cannot be printed until we have printed the rightmost
bit of 8 , and so on. Thus, the binary representation of 35 is the binary representation
of 17 (that is, the quotient of 35 after division by 2 ), followed by the rightmost bit
of 35 .
Thus, to convert a nonnegative integer num in base 10 into the equivalent binary
number, we first convert the quotient num / 2 into an equivalent binary number, and
then append the rightmost bit of num to the binary representation of num / 2 .
This discussion translates

1
3

into the following recursive algorithm, where

binary(num) denotes the binary representation of num :
1.

binary(num) = num if num = 0 .

2.

binary(num) = binary(num / 2) , followed by num % 2 if num > 0 .