Lab 3: Recursion

Task 0: Tracing a recursive function, part I

Recall the following recursive function from lecture:

def num_vowels(s):
    """ takes a string s of lower-case letters and returns
        the number of vowels in the string
        parameter:
          s -- a string of 0 or more lower-case letters
    """
    if s == '':
        return 0
    else:
        num_in_rest = num_vowels(s[1:])
        if s[0] in 'aeiou':
            return 1 + num_in_rest
        else:
            return 0 + num_in_rest

Let’s trace the execution of the following call to this function:

num_vowels('see')

We’ll trace this example together on paper, which will allow you to learn the method of tracing that the graders will be looking for on Problem 2 of Problem Set 2.

At the end of the lab, you should turn in your paper trace to the TF. To get credit for attendance at today’s lab, you must have made a good effort on this trace.

Task 1: Tracing a recursive function, part II

Consider the following recursive function:

def mystery(a, b):
    """ mystery does something and then returns something.
        parameters:
          a -- an int
          b -- an int
    """
    if a >= b:
        return b
    else:
        myst_rest = mystery(a * 2, b // 2)
        return a + myst_rest

Trace the execution of the following call to this function

mystery(1, 32)

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

mystery(1, 32)
--------------
    a = 1
    b = 32
    myst_rest = mystery(2, 16) = ...
    return ...

    mystery(2, 16)
    --------------
        a = 2
        b = 16
        myst_rest = ...
        return ...

        mystery(            )
        ---------------------
            a = ...
            b = ...
            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

Debugging is an essential skill in computer programming. We would like to emphasize some common debugging techniques and tips that will help you diagnose problems with your programs.

Download the file lab3task2.py, which contains the following num_consonants() function. We’ll see how to use these techniques to debug the function, which has one or more bugs.

def num_consonants(s):
    """ returns the number of consonants in s
        parameter: s is a string of lower-case letters
    """
    if s == ' ':
        return 0
    else:
        num_in_rest = num_consonants(s[1:])
        if s[0] not in 'aeiou':
            return num_in_rest
        else:
            return num_in_rest + 1

When we’ve finished debugging the function, leave any tracing print() statements in the file you upload to Apollo.

Task 3: Designing a recursive function

In this task, we will design and implement a recursive function that operates on a non-empty list.

More specifically, we will write a function min_val(values) that takes a non-empty list of values and uses recursion to find and return the smallest value in the list.

For example:

>>> min_val([5, 10, 7, 15])
5
>>> min_val([20, 6, 4, 10])
4
>>> min_val([10])
10

You may not use the built-in min function!

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:

   min_val([5, 10, 7, 15])

   • 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? (what is our one step?)

   min_val([20, 6, 4, 10])

   • 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? (what is our one step?)

3. What you need to do:

   1. Implement min_val(values) and store it in a file called lab3task3.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. Copy the test() function provided below into your lab3task3.py file, and add at least three test cases to the function.

      def test():
          """ test function for min_val() """
          test1 = min_val(['b', 'a', 'c'])
          print('test call 1 returns', test1)
      

Task 4: Designing recursive functions that do not return a value

In this task, we will design and implement recursive functions that do not return a value. Rather, they will simply do some printing.

More specifically, you will write two functions print_forward(s) and print_backward(s). Each function takes string s and uses recursion to print out the string one character at a time, forwards and backwards respectively. Note that these functions do not return a value, but rather use a print statement within the function.

Implement the functions in a file called lab3task4.py. Follow a procedure similar to the one used in the previous task to determine the logic of the functions. Include a docstring for each of them, and if you need help debugging, remember to take a look at the Debugging Tips page.

1. Write a function print_forward(s) that takes as input a string s and uses recursion to print the string s character by character.

   >>> print_forward('computer')
   c
   o
   m
   p
   u
   t
   e
   r
   
   >>> print_forward('science')
   s
   c
   i
   e
   n
   c
   e
   

   Hint: Because this function will not return a value, you should make the recursive call on its own line, without assigning the result to a variable.

2. Write a function print_backward(s) that takes as input a string s and uses recursion to print the string s character by character in reverse order.

   >>> print_backward('computer')
   r
   e
   t
   u
   p
   m
   o
   c
   
   >>> print_backward('science')
   e
   c
   n
   e
   i
   c
   s
   

3. Add at least three test calls to the bottom of the file.

If you have extra time!

Complete any of the problems listed under the List-1 collection of problems on CodingBat. These problems provide good practice with writing functions with lists.

Task 5: Submit your work

You should turn in the paper with your work on Task 0 to the teaching fellow.

You should use Apollo to submit the following files:

• your lab3task1.txt file containing your solution to Task 1
• your lab3task2.py file containing your solution to Task 2
• your lab3task3.py file containing your solution to Task 3
• your lab3task4.py file containing your solution to Task 3

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.