## CS 2401 Assignment #4

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:

1. A method that transforms a non-negative decimal integer into a binary number -- i.e., into a string of 0s and 1s.
2. 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:

• 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.
For example, to transform the number 13 into the binary code:
• 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.
As a result, the number 1310 is converted into a binary string 11012.

The following algorithm converts a binary string to a decimal 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.
For example, to transform the string 1101 into an integer:
• 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.