**Objective:** The goal of this assignment is to practice recursion.

**Problem to solve:** Converting a positive real number to binary code with
a given
number of binary digits after the (binary) point. The binary code should be
presented as a string of 0s and 1s, separated by the point.

**Example:** if we want to convert
the decimal number 13.125_{10} with four binary digits after the point,
we should get a string 1101.0010.

**Method: Part 1.** To covert a real number, we first extract its integer part (e.g.,
by using Java's *floor* method) and its fractional part -- e.g., by
subtracting the integer part from the number itself.

**Example:** when we apply *floor* to the number 13.125, we get the integer
part 13. By subtracting this integer part 13 from the original number, we then get
the fractional part 0.125.

**Method: Part 2.**
After we separate the integer and the fractional parts of the given number,
we separately convert the integer part and the fractional part into
binary.

The conversion of an integer part is described, in detail, in the Recursion chapter of our textbook. The corresponding algorithm is as follows:

- if the integer is 0 or 1, then we return a binary string consisting of the same symbol 0 or 1;
- otherwise, we divide the integer
*n*by 2, convert the value*n*/ 2 into binary (by using the same algorithm), and then - append the remainder
*n*% 2 to the resulting string.

**Example:** To convert *n* = 13, we first use the same method to convert
13 / 2 = 6 into binary, resulting in 110, and then append 13 % 2 = 1 to this string,
resulting in the binary code 1101.

To convert *n* = 6, the method first converts 6 / 2 = 3 into binary, resulting
in 11, and then appends 6 % 2 = 0 to this string, resulting in the binary code
110.

To convert *n* = 3, the method first converts 3 / 2 = 1 into binary, resulting
in 1, and then appends 3 % 2 = 1 to this string, resulting in the binary code
11.

Finally, when asked to convert *n* = 1 into binary, the method simply returns
the string consisting of a single binary digit 1.

**Method: Part 3.** For converting a fractional part, we can use
a similar algorithm but with multiplication by two instead of division by two:

- if we want the conversion into 0 binary digits, we simply return an empty string;
- to convert a number
*x*into*d*binary digits, we multiply the number by two, the integer part of2 * is the first digit, and the following*x**d*- 1 digits can be obtained by converting the fractional part of 2 **x*into*d*- 1 binary digits.

**Motivation:** For a fractional binary number like
*x* = 0.1101_{2}, multiplication by 2 means simply a shift (just like
for decimal numbers, multiplication by 10 is simply a shift), resulting in
2 * *x* = 1.101_{2}. The integer part of this number (1) is thus indeed
the first digit (1) of the binary expansion, and the remaining three digits 101
are the binary expansion of the fractional part 0.101_{2} of the value
2 * *x*.

**Example:** To convert *x* = 0.125 into *d* = 4 binary digits,
we compute
2 * *x* = 0.25. The integer part 0 of this fraction is the first digit of the
desired binary expansion, and the other *d* - 1 = 3 binary digits are
obtained by converting the fractional part 0.25 into 3 binary digits. This
conversion results in 010, so adding 0 as the first digit we get 0010.

To convert *x* = 0.25 into *d* = 3 binary digits,
we compute
2 * *x* = 0.5. The integer part 0 of this fraction is the first digit of the
desired binary expansion, and the other *d* - 1 = 2 binary digits are
obtained by converting the fractional part 0.5 into 2 binary digits. This
conversion results in 10, so adding 0 as the first digit we get 010.

To convert *x* = 0.5 into *d* = 2 binary digits,
we compute
2 * *x* = 1.0. The integer part 1 of this fraction is the first digit of the
desired binary expansion, and the other *d* - 1 = 1 binary digits are
obtained by converting the fractional part 0.0 into 1 binary digit. This
conversion results in 0, so adding 1 as the first digit we get 10.

To convert *x* = 0.0 into *d* = 1 binary digits,
we compute
2 * *x* = 0.0. The integer part 0 of this fraction is the first digit of the
desired binary expansion, and the other *d* - 1 = 0 binary digits are
obtained by converting the fractional part 0.0 into 0 binary digits. This
conversion results in an empty string (this is the base case of our recursion),
so adding 0 as the first digit we get 0.

**Assignment:** Write a program that implements the above recursion-using
algorithm to convert a real number into binary code with a given number of
binary digits after the binary point.