Problem Set 3: Introduction to Recursion

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: Thinking recursively

10 points; individual-only

Begin by downloading this file: ps3pr1.txt, and fill in your answers in this text file.

Consider the following recursive function:

def mystery(a, b):
    if a == b:
        return a
    else:
        myst_rest = mystery(a + 1, b - 2)
        return b + myst_rest

1. Trace the execution of the following call to this function

   mystery(0, 9)
   

   To do so, complete the template that we have provided in section 1-1 of ps3pr1. In particular, you should:

   • Include a separate “frame” for each call. We have filled in some of the components of the frames for the first two calls for you. You should replace each ... with the appropriate integer, and you should add frames for additional calls as needed, until you reach the base case.

   • Begin each frame with lines that explicitly state the values assigned to the parameters, as we have done for the first call.

   • Next, if the call is a base case, you can simply show the value that is returned (omitting the line for myst_rest). If the call is a recursive case, you should show the recursive call on the line for myst_rest.

   • Once you have reached the base case, you should work your way back through the frames for the previous calls. Add in both the results of the recursive call (i.e, the value assigned to myst_rest) and the value returned by the call itself.

2. What is the value returned by mystery(0, 9)?

3. During the execution of mystery(0, 9), stack frames are added and then removed from the stack. How many stack frames are on the stack when the base case is reached? You should assume that the initial call to mystery(0, 9) is made from the global scope, and you should include the stack frame for the global scope in your count.

4. Give an example of specific values of a and b that would produce infinite recursion, and explain why it would occur.

You may find it helpful to use the Python Tutor visualizer to build intuition about how recursion works, to check your answers to parts 1-3 of this problem, and to test and debug the functions that you write in the later problems. For example, to test the mylen function that we discussed in lecture, you could paste the following into the visualizer:

def mylen(s):
    if s == '':
        return 0
    else:
        len_rest = mylen(s[1:])
        return 1 + len_rest

test = mylen('cs111')
print('test is', test)

Problem 2: More practice writing non-recursive functions

20 points; individual-only

This problem involves more practice in writing non-recursive functions. These functions should be written without the use of recursion.

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

1. Write a function flipside(s) that takes a string input s and returns a string whose first half is s‘s second half and whose second half is s‘s first half. If len(s) (the length of s) is odd, the first half of the input string should have one fewer character than the second half, and thus the second half of the output string will be one character shorter in such cases. For example:

   >>> flipside('homework')
   'workhome'
   >>> print(flipside('carpets'))
   petscar
   

   Hint: We strongly recommend computing len(s)//2 (using the integer-division operator //) and storing the result in an appropriately named variable. You will need to use that value twice in your function, and using the variable in both places with save you from recomputing it.

   Warning

   Remember that your functions should return the correct value rather than printing it. If your function is printing the return value, you won’t see the quotes around the returned strings when you call the function on its own from the Shell, and you will see the word None as part of the output for the third test above. If this happens, you must fix your function so that it uses a return statement rather than a print statement. This same warning applies to all of the functions that you will write for this assignment unless we explicitly say otherwise.

2. Write a function adjust(s, length) that takes as inputs a string s and an integer length, and that returns a string in which the value of s has been adjusted as necessary to produce a string with the specified length.

   If s is too short, the value that is returned should be “padded” with spaces on the left-hand side:

   >>> adjust('alien', 6)
   ' alien'                 # pad with 1 space to get a length of 6
   >>> adjust('compute', 10)
   '   compute'             # pad with 3 spaces to get a length of 10
   

   If s is either the correct length or too long, the value that is returned should consist of the first length characters of s:

   >>> adjust('alien', 4)
   'alie'                   # return the first 4 characters
   >>> print(adjust('compute', 7))
   compute                  # return the first 7 characters -- all of it!
   

Problem 3: Fun with recursion, part I

30 points; pair-optional

See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

In this problem you will write three functions that employ the power of recursion!

In Spyder, open a new editor window for your program, and save it using the the name ps3pr3.py.

Here are the descriptions of the functions:

1. Write a function double(s) that takes an arbitrary string s as input, and that uses recursion to construct and return the string formed by doubling each character in the string. Here are three examples:

   >>> double('hello')
   'hheelllloo'
   >>> double('python')
   'ppyytthhoonn'
   >>> double('')
   ''
   

   This function is somewhat similar to the the replace function from lecture, because it needs to recursively create a new string from an existing string. However, your function will be simpler, because it won’t need to decide what to do after the recursive call returns.

2. Write a function copy(s, n) that takes as inputs a string s and an integer n, and that uses recursion to create and return a string in which n copies of s have been concatenated together.

   To force you to use recursion, you may not use the multiplication operator (*). Rather, you should use recursion to add together n copies of s. For example, 'hello'*3 is equivalent to 'hello'+'hello'+'hello', and you will need to use recursion to compute that sum.

   If n is less than or equal to 0, the function should return the empty string (i.e., the string '', which does not have any spaces between the quotes).

   Here are some test cases:

   >>> copy('da', 2)
   'dada'
   >>> print(copy('da', 2))
   dada
   >>> copy('Go BU!', 4)
   'Go BU!Go BU!Go BU!Go BU!'
   >>> copy('hello', 1)
   'hello'
   >>> copy('hello', 0)
   ''
   >>> copy('hello', -7)
   ''
   

   This function is similar to the power function from lecture. In that function, we reduce the value of p when we make the recursive call, but the value of b stays the same. In this problem, you will reduce one of the inputs to copy when you make a recursive call, and the other input will stay the same.

3. Write a function compare(list1, list2) that takes as inputs two lists of numbers, list1 andlist2, and that uses recursion to compute and return the number of values in list1 that are smaller than their corresponding value in list2. In other words, the function should compare list1[0] with list2[0], list1[1] with list2[1], list1[2] with list2[2], etc, and it should return the number of positions at which the value from list1 is smaller than the value from list2. For example:

   >>> compare([5, 3, 7, 9, 1], [2, 4, 7, 8, 3])
   2
   

   The above call returns 2, because:

   • in position 0, 5 > 2
   • in position 1, 3 < 4
   • in position 2, 7 == 7
   • in position 3, 9 > 8
   • in position 4, 1 < 3

   Thus, there are two positions (1 and 4) at which the value from list1 is smaller than the value from list2.

   Note that it is possible for the two lists to have different lengths, in which case the function should only compare the positions at which the two lists both have values.

   >>> compare([4, 2, 3, 7], [1, 5])      # 4 > 1; 2 < 5; can't compare 3 or 7
   1
   >>> compare([4, 2, 3], [6, 5, 0, 8])   # 4 < 6; 2 < 5; 3 > 0; can't compare 8
   2
   >>> compare([5, 3], [])
   0
   >>> compare([], [5, 3, 7])
   0
   

   This function is somewhat similar to the mylen function from lecture, but it needs to deal with lists instead of strings, and it needs to process two lists at the same time. You can find a modified version of mylen that handles both strings and lists here.

Problem 4: Fun with recursion, part II

25 points; individual-only

This problem provides more practice in writing functions, including three recursive functions.

In Spyder, open a new editor window for your program, and save it using the the name ps3pr4.py.

Follow the same guidelines that we gave you for Problem 3. For parts 2, 3 and 4, you must use recursion.

1. Write a function letter_score(letter) that takes a lowercase letter as input and returns the value of that letter as a scrabble tile. If letter is not a lowercase letter from ‘a’ to ‘z’, the function should return 0. This function does not require recursion.

   Here is the mapping of letters to scores that you should use:

   

   For example:

   >>> letter_score('w')
   4
   >>> print(letter_score('q'))
   10
   >>> letter_score('%')      # not a letter
   0
   >>> letter_score('A')      # not lower-case
   0
   

   We encourage you to begin with the following template:

   def letter_score(letter):
       """ your docstring goes here """
       assert(len(letter) == 1)
   
       # put the rest of your function here
   

   Note that we begin with an assert statement that validates the input for the parameter c. If the condition given to assert is not true–in this case, if the input provided for c has a length other than 1–then assert will cause your code to crash with an AssertionError. Using assert in this way can help you to find and debug situations in which you accidentally pass in incorrect values for the parameter of a function.

   Hints:

   • You will need to use conditional execution (if-elif-else) to determine the correct score for a given letter.

   • You can greatly reduce the number of cases if you use the in operator. For example:

     if letter in ['b', 'c', 'm', 'p']:   # letters with a score of 3
         return 3
     elif letter in ...
     

2. Write a function scrabble_score(word) that takes as input a string word containing only lowercase letters, and that uses recursion to compute and return the scrabble score of that string – i.e., the sum of the scrabble scores of its letters. For example:

   >>> scrabble_score('python')
   14
   >>> scrabble_score('a')
   1
   >>> scrabble_score('quetzal')
   25
   

   In addition to calling itself recursively, the function must also call your letter_score function to determine the score of a given letter. Doing so will allow you to avoid repeating the long if-elif-else statement that is already present in letter_score. Indeed, the only if-else statement that you should need is the one that determines whether you have a base case or recursive case.

3. Write a function add(vals1, vals2) that takes as inputs two lists of 0 or more numbers, vals1 and vals2, and that uses recursion to construct and return a new list in which each element is the sum of the corresponding elements of vals1 and vals2. You may assume that the two lists have the same length.

   For example:

   >>> add([1, 2, 3], [3, 5, 8])
   [4, 7, 11]
   

   Note that:

   • The first element of the result is the sum of the first elements of the original lists (1 + 3 –> 4).
   • The second element of the result is the sum of the second elements of the original lists (2 + 5 –> 7).
   • The third element of the result is the sum of the third elements of the original lists (3 + 8 –> 11).

   Here are some other examples:

   >>> add([2, 3, 4, 5], [-3, -2, -1, 0])
   [-1, 1, 3, 5]
   >>> add([], [])
   []
   

4. Write a function weave(s1, s2) that takes as inputs two strings s1 and s2 and uses recursion to construct and return a new string that is formed by “weaving” together the characters in the strings s1 and s2 to create a single string. In other words, the new string should alternate characters from the two strings: the first character from s1, followed by the first character from s2, followed by the second character from s1, followed by the second character from s2, etc. If one of the strings is longer than the other, its “extra” characters – the ones with no counterparts in the shorter string – should appear immediately after the “woven” characters (if any) in the new string.

   >>> weave('aaaaaa', 'bbbbbb')
   'abababababab'
   >>> weave('abcde', 'VWXYZ')
   'aVbWcXdYeZ'
   >>> weave('aaaaaa', 'bb')    # four extra 'a' characters at the end
   'ababaaaa'         
   >>> weave('aaaa', 'bbbbbb')  # two extra 'b' characters at the end
   'ababababbb'       
   >>> weave('aaaa', '')        # all of the 'a' characters are extra!
   'aaaa'       
   >>> weave('', 'bbbb')        # all of the 'b' characters are extra!
   'bbbb'       
   >>> weave('', '')        
   ''
   

   Hint: You will need more than one base case.

Submitting Your Work

You should use Gradesope to submit the following files:

• your modified ps3pr1.txt file containing your solutions for Problem 1
• your ps3pr2.py file containing your solutions for Problem 2
• your ps3pr3.py file containing your solutions for Problem 3
• your ps3pr4.py file containing your solutions for Problem 4

*   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.