Programming and Problem Solving with Java

(^642) | Recursion
It looks as though we can implement the solution to the problem with a straightfor-
ward iterative algorithm. Each remainder is obtained from the remainder operation (%in
Java), and each quotient is the result of the /operation.
Let’s do a walk-through to test this algorithm.
Number Remainder
42 0
21 1
10 0
51
20
11
(remainder from step 123456)
Answer: 010101
The answer is backwards! An iterative solution (using only simple variables) doesn’t
work. We need to print the last remainder first. The first remainder should be printed only
after the rest of the remainders have been calculated and printed.
In our example, we should print 42 % 2 after (42 / 2) % 2 has been printed. This, in turn,
means that we should print (42 / 2) % 2 after ((42 / 2) / 2) % 2 has been printed. Now our so-
lution begins to look like a recursive definition. We can summarize by saying that, for any
given number, we should print number% 2 after (number/ 2) % 2 has been printed.
What is the base case? We know the answer when numberis zero: We have finished and
have nothing left to do. What is the recursive case? Convert numberdivided by 2. When this
conversion is complete, print the remainder of numberdivided by 2 (number % 2). This solution
leads to the following algorithm:
If numberis 0, we have called convertas many times as necessary and can begin printing the
answer. The base case occurs when we do nothing. The recursive solution to this problem is
encoded in the following convertmethod.
convert (number)
ifnumber > 0
convert(number / 2)
Print number % 2
convert(number)
whilenumber > 0
Set remainder to number % 2
Print remainder
Set number to number / 2