Python assignment, code with comments required
Microsoft Word - Assignment 2-Recursion.docx Assignment 2 The Problem We are going to use recursion to do some conversions, from integer to binary and then from binary back to integer. Your Task Prompt the user to convert to binary or decimal and then get a number from the user. Write a recursive function to convert integer numbers to a binary number and print it as a string (there is no type for actual binary numbers so we just represent it as a string). Write a second function to take a string and convert it back into a regular integer and print it. Things to remember: 1. If the integer is 0, this is the base case since conversion back and forth of 0 is still 0. The program simply prints a note saying it is 0 and quits. 2. If the integer is negative, then we probably don’t know how to do it, so the program prints a message saying it is negative and quits. 3. Otherwise, do the conversion of the integer to a binary string (a string of 1’s and 0’s). 4. Convert that same string back to an integer to make sure we did it right. Hints How do we get a binary string from an integer? The easiest method uses integer division by 2 on successive quotients and then collects the remainders. It is best illustrated by an example. Consider the decimal number 156. • 156 divided by 2 gives the quotient 78 and remainder 0. • 78 divided by 2 gives the quotient 39 and remainder 0. • 39 divided by 2 gives the quotient 19 and remainder 1. • 19 divided by 2 gives the quotient 9 and remainder 1. • 9 divided by 2 gives the quotient 4 and remainder 1. • 4 divided by 2 gives the quotient 2 and remainder 0. • 2 divided by 2 gives the quotient 1 and remainder 0. • 1 divided by 2 gives the quotient 0 and remainder 1. Stop at reaching a quotient of 0. The binary equivalent is given by concatenating the remainders, in reverse (so the last remainder is the most significant bit and the first is the least). In this example: `10011100’ How do we get an integer from a binary string? First, we know it is a string, so the elements are ‘1’ and ‘0’. For every 1 in this string, we add a power of two to the overall decimal value. The power of 2 that we add depends on the position of the 1 in the binary string. A 1 in the far right (last) position of the string adds 2**0, in the next to last position adds 2**1, in the next to the next to the last position adds 2**2, and so on. If the bit is a ‘1’, then we add that power of 2 to the overall sum; if it is 0 we do nothing. For example, starting the last (right most) position of ‘10011100’ • last bit is ‘0’, so it contributes nothing to the sum. • next bit is ‘0’, so it contributes nothing to the sum. • next bit is ‘1’, so it contributes 2**2 to the sum. • next bit is ‘1’, so it contributes 2**3 to the sum. • next bit ‘1’, so it contributes 2**4 to the sum. • next bit is ‘0’, so it contributes nothing to the sum. • next bit is ‘0’, so it contributes nothing to the sum. • next bit is ‘1’, so it contributes 2**7 to the sum. The decimal equivalent is therefore 2**2 + 2**3 + 2**4 + 2**7, which equals 156. If you want to try something more challenging Can you take an integer and turn it into hexadecimal (base 16, see http://en.wikipedia.org/wiki/Hexadecimal ). Can you turn a hexadecimal string back into integer? Can you have the user enter the base as well as the integer and convert it to that base?