title: Lab 4: More recursion!
[TOC]
### Task 0: Tracing a recursive function, part I ###
Recall the following recursive function from lecture:
:::python
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:
:::python
num_vowels('ate')
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 1 of [Problem Set 3](../problem_sets/ps3.html).
***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:
:::python
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:
:::text
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`][lab4task2]**, which contains the
following buggy version of a `count()` function.
:::python
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:
:::text
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:
:::text
RecursionError: maximum recursion depth exceeded
This indicates that you are getting infinite recursion!
Use one or more [debugging techniques][debugging] to diagnose
the problems in this function. Ultimately, the function should pass all of
the following test cases:
:::text
>>> 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:
:::python
>>> 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][debugging] 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*** to the bottom of the file.
For example:
:::python
print("remove_spaces('a b c d') returns", remove_spaces('a b c d'))
Note that we need to surround the string literal that we are
printing with *double quotes*, because that string literal
includes single quotes inside it.
### Task 4: OPTIONAL design challenge ###
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:
:::python
>>> 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
:::python
myslice(['a', 'b', 'c', 'd', 'e'], 2, 4)
is equivalent to
:::python
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][debugging] page.
### 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 `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
* if you worked on the optional challenge, your `lab4task4.py` file
containing your solution to Task 4
***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. Find the appropriate lab section on the main page and
click *Upload files.*
3. 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.
4. Click the *Upload* button at the bottom of the page.
5. 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.
6. 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.***
[lab4task2]: ../files/labs/lab4/lab4task2.py
[debugging]: ../problem_sets/debugging.html