Problem Set 4: Building our Recursion Muscles

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

For each problem in this problem set, we will be writing or evaluating some Python code. You are encouraged to use the Spyder IDE which will be discussed/presented in class, but you are welcome to use another IDE if you choose.

If you have questions while working on this assignment, please post them on Piazza! This is the best way to get a quick response from your classmates and the course staff.

If you have questions while working on this assignment, please post them on Piazza! This is the best way to get a quick response from your classmates and the course staff.

Problem 1: From binary to decimal and back!

20 points; individual-only

This problem asks you to write functions related to the binary representation of integers. We will use strings consisting of '0's and '1's for the binary numbers. For example, the binary representation of the integer 5 would be the string '101'.

In Spyder, use the File -> New File menu option to open a new editor tab for your code, and save it using the name ps4pr1.py.

The guidelines that we gave you for Problem Set 3, Problem 2 also apply here. In addition, you must use recursion in your solutions, and you may not use loops or list comprehensions.

Decimal to Binary Conversion

1. Write a function dec_to_bin(n) that takes a non-negative integer n and uses recursion to convert it from decimal to binary – constructing and returning a string version of the binary representation of that number. For example:

   >>> dec_to_bin(5)
   '101'
   >>> dec_to_bin(12)
   '1100'
   

   Notes/hints:

   • The function must use the recursive, right-to-left approach that we discussed in the lecture on binary numbers.

   • You will need two base cases: one for when n is 0, and one for when n is 1. Remember that you should always check for the base cases first.

   • In lecture, we gave you an example of how the function should recursively process a number. You should use that example to determine the appropriate logic for the recursive case.

   • Because we’re taking a right-to-left approach, the input to the recursive call should be the decimal number that’s produced when you remove the rightmost bit from n‘s binary representation. For example, if n is 9 (which has the binary representation '1001'), the recursive call should be on the number 4 (which has the binary representation '100'). In lecture, we discussed two options for obtaining the necessary number.

   • We encourage you to make the recursive call at the start of the recursive case and store its return value in a variable. Then you can use that variable to construct the string that you will return.

   • Remember that the rightmost bit of n‘s binary representation depends on whether n is even or odd. You can use the % operator to figure this out.

   • Here are some additional test cases:

     >>> dec_to_bin(0)
     '0'
     >>> dec_to_bin(1)
     '1'
     >>> dec_to_bin(4)
     '100'
     >>> dec_to_bin(7)
     '111'
     >>> dec_to_bin(10)
     '1010'
     >>> dec_to_bin(111)
     '1101111'
     

Binary to Decimal Conversion 2. Write a function bin_to_dec(b) that takes a string b that represents a binary number and uses recursion to convert the number from binary to decimal, returning the resulting integer. For example:

    :::python
    >>> bin_to_dec('101')
    5
    >>> bin_to_dec('1100')
    12

**Notes/hints:**

   * **The function must use the *recursive, right-to-left* approach 
     that we discussed in the lecture on binary numbers.**

   * You will again need two base cases: one for the string
     `'0'`, and one for the string `'1'`. You may assume
 that the string passed in for `b` will never be empty.

   * In lecture, we gave you an example of how the function should 
     recursively process a string. You should use that 
 example to determine the appropriate logic for your recursive case.

   * You should use slicing to obtain the string needed for the 
     recursive call. Because we're taking a right-to-left approach,
 the slice should give you everything but the rightmost bit. 
 Here again, we encourage you to make the recursive call 
 at the start of the recursive case and store its return value 
 in a variable. Then you can use that variable to construct the 
 value that you will return.

   * Don't forget that the value obtained from the recursive call will
     be the decimal value of a smaller number, and you will need
 to adjust it accordingly. See the lecture notes for a reminder
 of how to do this.

   * Here are some additional test cases:

        :::python
        >>> bin_to_dec('0')
        0
        >>> bin_to_dec('1')
        1
        >>> bin_to_dec('100')
        4
        >>> bin_to_dec('111')
        7
        >>> bin_to_dec('1110')
        14
        >>> bin_to_dec('00011010')
        26
        >>> bin_to_dec('1111111')
        127

Problem 2: Using your conversion functions

30 points; individual-only

In Spyder, use the File -> New File menu option to open a new editor tab for your code, and save it using the name ps4pr2.py.

The guidelines that we gave you for Problem Set 3, Problem 2 also apply here. You should not use recursion in these functions.

Important: Your should include the following line at the top of the file, after your initial comments:

from ps4pr1 import *

Doing so will allow you to use the dec_to_bin() and bin_to_dec() functions that you wrote for problem 1, provided that your ps4pr1.py file is in the same folder as your ps4pr2.py file.

1. Write a function add(b1, b2) that takes as inputs two strings b1 and b2 that represent binary numbers. The function should compute the sum of the numbers, and return that sum in the form of a string that represents a binary number. For example:

   >>> add('11', '1')
   '100'
   >>> add('11100', '11110')
   '111010'
   

   In this function, you should not need to use recursion or to perform any binary arithmetic. Rather, you should make use of the conversion functions that you wrote for Problem 1. If you included the line mentioned above to import your code from pr4pr1.py, you should be able to call your dec_to_bin and bin_to_dec functions from within this function. Convert both b1 and b2 to decimal, add the resulting decimal numbers, and then convert the resulting sum back to binary! Here is the pseudocode:

   n1 = the decimal value of the input string b1 (use one of your conversion functions!)
   n2 = the decimal value of the input string b2 (use that function again!)
   b_sum = the binary value of (n1 + n2) (use your other function!)
   return b_sum
   

2. Write a function increment(b) that takes an 8-character string representation of a binary number and returns the next larger binary number as an 8-character string. For example:

   >>> increment('00000000')
   '00000001'
   >>> increment('00000001')
   '00000010'
   >>> increment('00000111')
   '00001000'
   >>> increment('11111111')
   '00000000'
   

   Notes/hints:

   • As shown in the last example above, you will need a special case for when the input is '11111111'. This is the largest binary number that can be represented using 8 bits, so incrementing it causes the value to “wrap around” to give you '00000000'. Your function should start by testing for this special input, and it should handle it by simply returning the appropriate value.

   • Here again, you should not use recursion or perform any binary arithmetic. Rather, you should make use of the conversion functions that you wrote for Problem 1.

   • To ensure that your result has the correct length, we encourage you to do the following:

     • Use your conversion functions to determine the binary representation of the result, and store that result in a variable.

     • Determine the length of the result using the len() function, and store that length in a variable.

     • If the result is less than 8 bits long, precede the result with the correct number of leading '0's. You can use the multiplication operator to produce the necessary string of '0's.

Problem 3: Recursive operations on binary numbers

30 points; individual-only

This problem asks you to write two different recursive functions that manipulate binary numbers.

In Spyder, use the File -> New File menu option to open a new editor tab for your code, and save it using the name ps4pr3.py.

The guidelines that we gave you for Problem Set 3, Problem 2 also apply here. In addition, you must use recursion in your solutions, and you may not use loops or list comprehensions.

1. The bitwise AND of two binary numbers is formed by considering the bits in the numbers from right to left. As you do so, each pair of corresponding bits is ANDed together to produce the appropriate bit for the result.

   For example, to obtain the bitwise AND of 11010 and 10011, we would begin by essentially lining up the two numbers as follows:

   	1	1	0	1	0
   	1	0	0	1	1

   We would then AND together each pair/column of bits from right to left. For example, the rightmost column gives us (0 AND 1) which is 0:

   	1	1	0	1	0
   	1	0	0	1	1
   					0

   The next pair/column of bits gives us (1 AND 1) which is 1:

   	1	1	0	1	0
   	1	0	0	1	1
   				1	0

   Continuing in this way, we get:

   	1	1	0	1	0
   	1	0	0	1	1
   	1	0	0	1	0

   And thus the bitwise AND of 11010 and 10011 is 10010.

   If one number has more bits than the other, the extra bits are effectively ANDed with 0s, and thus they lead to 0s in the result. For example:

   	1	0	0	1	1	1	1
   			1	1	0	1	1
   	0	0	0	1	0	1	1

   Write a function called bitwise_and(b1, b2) that takes as inputs two strings b1 and b2 that represent binary numbers. The function should use recursion to compute the bitwise AND of the two numbers and return the result in the form of a string. For example:

   >>> bitwise_and('11010', '10011')
   '10010'
   >>> bitwise_and('1001111', '11011')
   '0001011'
   

   Notes/hints:

   • Base cases: Because the function will be called recursively on smaller and smaller strings, you will eventually get down to an empty string for one or both of the inputs.

     • If both inputs are the empty string, the function should return the empty string.

     • If only one of the inputs is the empty string, the function should return a string that represents the result of ANDing the other input with 0s.

     For example:

     >>> bitwise_and('', '')
     ''
     >>> bitwise_and('101', '')
     '000'
     >>> bitwise_and('', '11010')
     '00000'
     

     Hint: Use string multiplication to obtain a string with the appropriate number of 0s.

   • You should use recursion to AND the rest of the bits in the two numbers. When you do so, make sure that you end up considering the bits from right to left, rather than from left to right.

   • As usual, we recommend making the recursive call at the start of the recursive case and storing its return value in a variable. Then you can use that variable to construct the value that you will return.

   • You will need to use conditional execution (if-else or if-elif-else) to decide what to return, based on the bits that are being ANDed by the current call of the function. Use concrete cases as needed to figure out the logic.

Bitwise Addition of Binary Numbers

2. Write a function called add_bitwise(b1, b2) that adds two binary numbers. This function must use recursion to perform the bitwise, “elementary-school” addition algorithm that we discussed in lecture, and it should return the result. It should not perform any base conversions, and it should not call the add_bytes function from Problem 2.

   Your function should add one pair of bits at a time, working from right to left and including any necessary “carry” bits, as discussed in lecture. For example, when adding 101110 and 100111, you end up with 3 carry bits, as shown in blue below:

   			1	1	1
   		1	0	1	1	1	0
   +		1	0	0	1	1	1
   	1	0	1	0	1	0	1

   Notes/hints:

   • Base cases: Because the function will be called recursively on smaller and smaller strings, you will eventually get down to an empty string for one or both of the inputs. If either of the strings (b1 or b2) is the empty string, your function should return the other string.

   • You should use recursion to add the rest of the numbers. Here again, we recommend making the recursive call at the start of the recursive case and storing its return value in a variable. Then you can use that variable to construct the value that you will return.

   • You will need to use conditional execution (if-elif-else) to decide what to return, based on the bits that are being added by the current call of the function.

   • Handling cases that require a carry bit can be the most difficult part of this problem. The trick is to call the function recursively a second time to add in the carry bit!

   • Here are some test cases:

     >>> add_bitwise('11100', '11110')
     '111010'
     >>> add_bitwise('10101', '10101')
     '101010'
     >>> add_bitwise('11', '1')
     '100'
     >>> add_bitwise('11', '100')
     '111'
     >>> add_bitwise('11', '')
     '11'
     >>> add_bitwise('', '101')
     '101'
     

Submitting Your Work

You should use Gradesope to submit the following files:

• your ps4pr1.py file containing your solutions for Problem 1
• your ps4pr2.py file containing your solutions for Problem 2
• your ps4pr3.py file containing your solutions for Problem 3

*   Why does this happen? When the autograder imports your file, the `print` 
    statement(s) execute (at import time), which causes this error.

*   You can prevent this error by not having any `print` statements in the global scope.
    Instead, create an `if __name__ == '__main__':` section at the bottom of the file, and
    put any test cases/print statements in that controlled block. For example:

        if __name__ == '__main__':

            ## put test cases here:
            print('future_value(0.05, 2, 100)', future_value(0.05, 2, 100))

*   `print` statements inside of functions do not cause this problem.