Due Date: Monday, March 7 or Tuesday, March 8, depending on the day of your lab.
Objective: The goal of this assignment is to practice recursion.
Assignment: Write the following two methods:
- A method that transforms a non-negative decimal integer into a binary number -- i.e., into a string of 0s and 1s.
- A method that takes a string of 0s and 1s and transforms it into a decimal integer.
Details: The main ideas behind the corresponding recursive
methods are similar to the ones described in Section 7.3.1 of the textbook.
The following algorithm translates the number n into a string of 0s and 1s:
For example, to transform the number 13 into the binary code:
- If a number is 0 or 1, produce a string consisting of the same single character (correspondingly, 0 or 1).
- If the number n is larger than 1:
- divide n by 2,
- convert the ratio n / 2 to binary, and
- append the remainder n % 2 at the end.
As a result, the number 1310 is converted into a binary string 11012.
- compute 13 / 2 = 6,
- convert 6 into binary code (by using the same algorithm) -- the result will be 1102;
- then append the remainder 13 % 2 = 1 at the end of this string -- the result will be 11012.
The following algorithm converts a binary string to a decimal integer:
For example, to transform the string 1101 into an integer:
- If the string consists of only one character, i.e., it is 0 or 1, return the corresponding number (0 or 1).
- If the string has more than one character:
- convert the substring consisting of all the characters but the last one into an integer,
- then multiply this integer by 2, and
- add the number equal to the last digit.
- convert the substring 110 into an integer (by using the same algorithm) --the result will be 6;
- then multiply 6 by 2, resulting in 12, and
- add the number 1 (equal to the last character of the original string 1101) -- the result will be 13.
As a result, the binary string 1101 is converted into the number 13.
For extra credit: Modify your methods so that, instead
of only binary (base 2) representations, we will be able to process base 3, base 4, ..., base 10 representations.