Contents

Overview

We have just learned about recursion. The goal of this assignment is to give you practice applying a divide-and-conquer strategy to problems and using that to establish a recursive solution. This assignment consists of several unrelated problems, but that you will implement in a single C++ program. You will start from the partially implemented skeleton below. The skeleton includes a function to interact with the user to test the various solutions you've come up with. You need to implement the portions with comments that read // TODO: IMPLEMENT THIS..

There are four problems you need to implement, and you can create additional functions if you need (e.g., to implement multiple recursion if that's required by your solution). They are:

• Modulo (remainder): given two integer operands a and b, provide the remainder after dividing a by b. E.g., mod(5, 3) is 2. Do not simply use the mod (%) operator; your solution must be recursive.
• Inserting commas: given an integer (or long) of any length, add commas at the appropriate points. E.g., insertCommas(1000) returns the string "1,000" and insertCommas(900) returns "900". I am providing you with a function that converts an integer to a string so that you can easily concatenate integers and strings. It should work with positive and negative numbers.
• Minimum numeric positions (log rounded up): given a base 10 integer operand x and a base b, calculate the number of positions (digits) it will take to represent x in base b. Note this is equivalent to computing log_b(x) and rounding up to the nearest whole integer. Log simply tells you exactly how many times the base b needs to be multiplied by itself to produce the operand x. So minPositions(15, 2) gives us 4 because we need 4 positions to represent 4 in binary (i.e., 1111). To get 4, we count how many times we need to divide 15 by 2 until we reach 1 or lower: 16 / 2 = 8; 8 / 2 = 4; 4 / 2 = 2; 2 / 2 = 1—we performed 4 divisions. If we change our base to 10, the minPositions() function will tell us how many positions our decimal operand takes up; if we change our base to 16, it will tell us the number of positions we need in hexadecimal format. You may not use math libraries, e.g., log, to solve this; just the basics operators (+, -, *, /).
• Convert decimal (base 10) to binary (base 2): given a base 10 integer, convert it into binary. For example, toBinary(15) should return the string "1111", which is 15 (base 10) in binary (base 2). You will probably want to make use of the minPositions() function above to find the minimum number of positions required. Each position can be given a decimal value, which is b^(pos-1), where pos is the position number starting from the right. So in our example converting 15 to binary, we need 4 positions, the left-most one of which is 2^(4-1) and the the right-most position is 2^(1-1). The algorithm starts with a remainder value equal to the input decimal value, and works its way left to right down the positions. At each step, we are trying to determine if the position should be a 1 or a 0. The position is 1 if when we subtract the current position's decimal value from the current remainder value, we get a non-negative value. If so, we update our current remainder value to be that difference. Otherwise, we keep the remainder value the same. In both cases, we move to the next value.

Here's an example of my version of PA1 running (my input is in orange just to make it obvious):

$ ./pa1 
Pick an operation to perform. One of: 
    mod a b (mod a by b)
    commas a    (insert commas into a)
    minPos x b  (find the min. positions to represent x in base b)
    toBinary x  (convert x to binary)
    quit    (exit)
: mod 13 2
1

Pick an operation to perform. One of: 
    mod a b (mod a by b)
    commas a    (insert commas into a)
    minPos x b  (find the min. positions to represent x in base b)
    toBinary x  (convert x to binary)
    quit    (exit)
: commas 29293484
29,293,484

Pick an operation to perform. One of: 
    mod a b (mod a by b)
    commas a    (insert commas into a)
    minPos x b  (find the min. positions to represent x in base b)
    toBinary x  (convert x to binary)
    quit    (exit)
: minPos 127 2
7

Pick an operation to perform. One of: 
    mod a b (mod a by b)
    commas a    (insert commas into a)
    minPos x b  (find the min. positions to represent x in base b)
    toBinary x  (convert x to binary)
    quit    (exit)
: toBinary 127
1111111

Pick an operation to perform. One of: 
    mod a b (mod a by b)
    commas a    (insert commas into a)
    minPos x b  (find the min. positions to represent x in base b)
    toBinary x  (convert x to binary)
    quit    (exit)
: quit
Bye!

(Back to top)

Requirements

• Each of the four functions must be implemented using recursion. You can create and use additional functions if you think it will be helpful
• Everything in the rubric (posted on Canvas) should be followed
• Make sure to follow the style guidelines

Here's a skeleton to get you started:

(Back to top)

Extra credit

Make sure you indicate in your program header (in the description) whether you've attempted the extra credit, otherwise I won't count it!!!

EC-1 (2 points)

Make a new recursive function to convert a decimal into octal (0–7) or hexadecimal (0–f).

(Back to top)

Submissions

Everything should be uploaded to Canvas by the deadline posted.

(Back to top)