Lab 4: More recursion!

Task 1: More practice tracing a recursive function

Consider the following recursive function:

def mystery(values):
    """ mystery does something and then returns something.
        parameters:
           values -- a list of 0 or more numbers
    """
    if values == []:
        return []
    else:
        myst_rest = mystery(values[1:])
        if values[0] < 0:
            return myst_rest + [values[0]] 
        else:
            return [values[0]] + myst_rest

Trace the execution of the following call to this function

mystery([7, -2, -8, 10])

To do so, create a text file named lab4task1.txt and begin by copying the following template into that file:

mystery([7, -2, -8, 10])
------------------------
    values = [7, -2, -8, 10]
    myst_rest = mystery([-2, -8, 10]) = ...
    return ...

    mystery([-2, -8, 10])
    ---------------------
        values = [-2, -8, 10]
        myst_rest = ...
        return ...

        mystery(            )
        ---------------------
            values = ...
            myst_rest = ...
            return ...

Complete this template so that it traces the series of recursive calls. In particular, you should:

• Include a separate section for each call. We have filled in some of the components of the first two calls for you, and we have given you a template for the third call. You should add sections for additional calls as needed, all the way down to the base case.

• Begin each section with a line that explicitly states the value assigned to the parameter, as we have done for the first two calls.

• 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 (as we have done for the first call).

• Once you have reached the base case, you should work your way back through the sections 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.

Task 2: Debugging a recursive function

Download the file lab4task2.py, which contains the following buggy version of a count() function.

def count(val, values):
    """ returns the number of times that val is found in the list values
        parameters:
            val -- an arbitrary value
            values -- a list of 0 or more arbitrary values
    """
    if len(values) == 1 and values[0] == val:
        return 1
    else:
        count_in_rest = count(val, values[:1])
        if values[0] == val:
            return count_in_rest
        else:
            return count_in_rest + 1

This function is supposed to return a count of the number of times that the value val is found in the list values. However, the current version doesn’t work!

For example, run the file and try the following call from the Shell:

count(5, [4, 5, 7, 5])

If the function were working, it would return 2. Instead you should see a long series of messages ending with something like the following:

RecursionError: maximum recursion depth exceeded

This indicates that you are getting infinite recursion!

Use one or more debugging techniques to diagnose the problems in this function. Ultimately, the function should pass all of the following test cases:

>>> count(5, [4, 5, 7, 5])
2
>>> count(5, [4, 5, 7])
1
>>> count(5, [4, 6, 7])
0
>>> count(5, [])
0

Task 3: Designing a recursive function

In this task, we will design and implement a recursive function that removes all spaces from a string.

More specifically, we will write a function remove_spaces(s) that takes string s and that uses recursion to construct and return a string in which all of the spaces have been removed.

For example:

>>> remove_spaces('hi how are you?')
'hihowareyou?'
>>> remove_spaces('    fine thanks!   ')
'finethanks!'

1. Let’s start by determining the base case(s). When is the problem simple/small enough to be solved directly (without first solving a smaller subproblem)?

2. Next, we need to design the recursive case. In doing so, it helps to consider some concrete cases. For example:

   remove_spaces('a b c d')

   • what is the solution?
   • what is the next smaller subproblem?
   • what is the solution to that subproblem?
   • how can we use the solution to the subproblem to construct the solution to the original problem?

   remove_spaces(' b c d')

   • what is the solution?
   • what is the next smaller subproblem?
   • what is the solution to that subproblem?
   • how can we use the solution to the subproblem to construct the solution to the original problem?

3. What you need to do:

   1. Implement remove_spaces(s) and store it in a file called lab4task3.py. If you need help debugging your function, remember to take a look at the Debugging Tips page.

   2. Remember to add a docstring to the function that describes its behavior, its parameters, and its return value.

   3. Add at least three test cases in a test function at the bottom of the file. For example:

      def test():
          test1 = remove_spaces('a b c d')
          print('first test returns', test1)
      

Task 4: Writing functions that use lists-of-lists

Begin by creating a new file in IDLE named lab4task4.py, and use it for your work on this task.

In Problem Set 2, you wrote several functions that used a list comprehension. In Problem Set 3, you will write several others, including some that use the list-of-lists technique discussed in lecture.

0. Begin by entering the following list comprehension from the Shell:

   >>> [len(w) for w in ['hello', 'bye', 'hi']]
   

   What do you see? Make sure that you understand why the result makes sense, and ask a staff member if you are unsure.

1. Now let’s say that we want to find the longest word from a list of words. We can use the list-of-lists technique that we saw in lecture. To recall how it works, try entering the following sequence of lines from the Shell:

   >>> pairs = [[len(w), w] for w in ['hello', 'bye', 'hi']]
   >>> pairs
   
   >>> max(pairs)
   

   What do you see? Here again, make sure that the outputs make sense, and ask questions as needed.

2. Next, copy the following template into your lab4task4.py file:

   def longest_word(wordlist):
       """ returns the longest word from the wordlist passed in as 
           a parameter
       """
       pairs = [[len(w), w] for w in ____________]
       bestpair = max(pairs)
       return ____________
   

   Fill in the blanks to produce a function that takes in an arbitrary list of words and that returns the longest word.

   Once you think you have it working correctly, run the file and test it:

   >>> longest_word(['hello', 'bye', 'hi'])
   'hello'
   >>> longest_word(['I', 'love', 'Python'])
   'Python'
   

   Ask for help as needed!

3. You will now use this list-of-lists approach to write a function that processes a list of numbers. However, rather than always returning the same type of result, your function will include an input that allows the user to choose among two possible results.

   Start by copying the following helper function into lab4task4.py:

   def square(value):
       sq = value**2
       return sq
   

   Now write a function process_squares(values, choice) that takes two inputs: a list of integers values and a single integer choice. It should use the list-of-lists technique and the square helper function to return one of two possible results. The value returned should be based on the value of the input choice as follows:

   choice      value returned
   ------      --------------
      1        the largest of the squares of the integers in values
      2        the integer from values whose square is the largest
   

   Examples:

   >>> process_squares([2, 3, -4, -1], 1)    
   16
   >>> process_squares([2, 3, -4, -1], 2)
   -4    
   >>> process_squares([-2, 5, 3], 1)    
   25
   >>> process_squares([-2, 5, 3], 2)    
   5
   

   Hint: Begin by forming an appropriate list of lists. Make sure that the order of the elements in the sublists allows you to determine the largest square. Then use conditional logic to decide which value to return.

4. Optional extensions: What changes would be needed if you wanted the function to be flexible enough to choose between processing all elements in values, only the even elements in values, or only the odd elements? See if you can create this more flexible version!

If you have extra time!

In this optional challenge problem, we will implement a recursive function that has the same behavior as the list slice operator.

More specifically, we will write a function myslice(values, start, stop) that takes list values and two index values start and stop, and that uses recursion to construct and return the equivalent of values[start:stop] – i.e., the slice of values that begins with the element at index start and that goes up to but not including the element at index stop.

For example:

>>> values = ['a', 'b', 'c', 'd', 'e']
>>> myslice(values, 2, 4)     # should return equivalent of values[2:4]
['c',  'd']
>>> myslice(values, 1, 5)     # should return equivalent of values[1:5]
['b', 'c', 'd', 'e']
>>> myslice(values, 3, 3)     # should return equivalent of values[3:3]
[]

Your implementation must be recursive, and the only list operations you are allowed to use are accessing the first element of the list (values[0]) and accessing all elements except the first (values[1:]).

You do not need to worry about negative or omitted index values or the use of a stride length.

1. Start by determining the base case(s). When is the problem simple/small enough to be solved directly (without first solving a smaller subproblem)?

2. Next, design the recursive case by considering concrete cases.

   In doing so, it’s important to realize that when you reduce the list to a smaller list, you also need to adjust one or both of the index values! For example, the problem

   myslice(['a', 'b', 'c', 'd', 'e'], 2, 4)
   

   is equivalent to

   myslice(['b', 'c', 'd', 'e'], 1, 3)
   

   Note that because the list has been shortened, we need to adjust the index values in order to continue getting the result ['c', 'd'].

   Here are some other concrete cases for you to think through:

   myslice(['to', 'be', 'or', 'not', 'to', 'be'], 1, 4)

   • what is the solution?
   • what is the next smaller subproblem?
   • what is the solution to that subproblem?
   • how can we use the solution to the subproblem to construct the solution to the original problem?

   myslice([6, 5, 4, 3, 2, 1], 0, 3)

   • what is the solution?
   • what is the next smaller subproblem?
   • what is the solution to that subproblem?
   • how can we use the solution to the subproblem?

3. Implement the myslice(values, start, stop) function and store it in a file called lab4task4.py. Remember to add a docstring to the function that describes its behavior, its parameters, and its return value.

If you need help debugging your function, remember to take a look at the Debugging Tips page.

Task 5: Submit your work

You should use Apollo to submit the following files:

• your lab4task1.txt file containing your solution to Task 1
• your lab4task2.py file containing your solution to Task 2
• your lab4task3.py file containing your solution to Task 3
• your lab4task4.py file containing your solution to Task 4
• if you worked on the optional challenge, your lab4task5.py file containing your solution to Task 5

Don’t worry if you didn’t finish all of the tasks. You should just submit whatever work you were able to complete during lab.

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate lab section on the main page and click Upload files.
4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
5. Click the Upload button at the bottom of the page.
6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.