Problem Set 3

due by 10 p.m. on Saturday, September 9, 2023

suggested self-deadline of Friday, September 8, 2023

Preliminaries

pair-optional or group-of-3-optional You may complete this entire assignment with a partner or within a group of 3. See the rules for working with partners on problems for details about how this type of collaboration must be structured.

If you have questions while working on this assignment, please post them on Piazza or come to TA Help Hours.

Make sure to submit your work on Gradescope.

Problem 1: Thinking recursively

20 points;

We suggest you watch this video on recursive function tracing first.

Begin by opening the Google Docs file: ps3pr1, and creating a copy. Rename the Copy of ps3pr1 back to ps3pr1. Use this file to fill in your answers to this problem.

When you are done, select File -> Download -> PDF Document (.pdf). Ensure that your file is named ps3pr1.pdf

If you do not use Google at all, you may use a Microsoft Word version instead. Open in Desktop App or select Download from the menu. When you are done, save the final result as ps3pr1.pdf.

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:

   • Fill in the “frame” for each call. You should add frames for additional calls as needed, until you reach the base case.

   • Each frame should show the values assigned to the parameters.

   • If the call is a base case, you can simply show the value that is returned ( noting that myst_rest is not executed). If the call is a recursive case, you should show the recursive call 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('cs120')
print('test is', test)

Problem 2: More practice writing non-recursive functions

20 points

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

In VS Code, use the File -> New File menu option to open a new editor window 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 interactive window, 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

25 points

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

In VS Code, 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 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 Clark!', 4)
   'Go Clark!Go Clark!Go Clark!Go Clark!'
   >>> 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.

2. 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 index 0: 5 > 2
   • in index 1: 3 < 4 –> add 1
   • in index 2: 7 == 7
   • in index 3: 9 > 8
   • in index 4: 1 < 3 –> add 1

   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.

3. 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 the linked example file, 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.

Problem 4: Fun with recursion, part II

30 points

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

In VS Code, 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 string of length 1 as input, and if the string is a lowercase letter from ‘a’ to ‘z’ the function returns the value of that letter as a scrabble tile. Otherwise the function returns 0 (to handle cases of uppercase letters or other characters such as ‘@’). 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’, 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.pdf 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

**if you worked with partners on the entire assignment, submit a single copy of your joint work, tag each partner within Gradescope after submitting, and include comments at the top of the file specifying the name and email of each partner.

if you worked with partners on only part of the assignment, each partner should submit individually. Include the name and email address of the partners on the parts that were joint collaboration.