CS21 Lab 11: Recursion!
Due Friday, April 22, at the start of class Recursion Worksheet
Due Saturday, April 23, by 11:59pm
In this lab you will write and test iterative and recursive versions of several functions that take numeric, list, or string values. You will also design test cases to test the correctness of your functions.
Goals

solving problems using recursion

writing test case to check for correctness

practice with programs with command line arguments

more practice with file I/O
Requirements
The following are the main requirements of this lab:

Your recursive functions should not have any loops in them (the recursive call takes the place of the loop)

Your iterative and recursive versions of each function should produce the same result.

You should test your programs on multiple input values to ensure correctness.

You will include your test cases as part of your submission for this lab (for the last program).

Your functions should have complete function comments, and be well designed.
Testing
For each program, you should come up with some good examples to test the correctness of your solution. Some of your testing examples, will be submitted with your lab (for the last program).
For the first two programs you will write both recursive and iterative versions of the same function, testing that they both do the same thing (return the same values) when called with the same argument values.
1. Recursion Worksheet
Print out the following worksheet, answer the questions on it, and submit it at the start of class on Friday April 22: recursion worksheet
2. Recursion on Numbers
In the file recursive_nums.py
, implement an iterative and a recursive version
of the following two functions:

Compute the Sum of the Even numbers from 1 to n. Implement the functions
sum_of_evens_iter(n)
andsum_of_evens_recursive(n)
that take an integer input valuen
and return the sum of all the even numbers between1
andn
inclusive.Create some test cases to test the correctness of these functions, calling them from
main
. 
Compute the Sum of the following series, for a given int value of
n
:\( \frac{1}{2^{1}} + \frac{1}{2^{2}} + \frac{1}{2^{3}} + \frac{1}{2^{4}} + ... + \frac{1}{2^{n}}\)
In
sum_series_iter(n)
andsum_series_recursive(n)
implement an iterative version and a recursive version of a function to compute the sum of this series.Create some test cases to test the correctness of these functions, test them out by running your program with different values for n (you could also add aditional calls from
main
to your functions to test them out).That the sum of this series, for any value of n greater than 0, will be a floating point value between 0.5 and 1.0.
Infinite Series in Math vs. in Computer Programs
In mathematics the sum of this sequence of infinite number of terms is 1:
\( \sum_{i=1}^{\infty} \frac{1}{2^{i}} = 1\)
This is an example of a geometric series, and in particular, this geometric series is related to Zeno’s dichotomy paradox.
When we sum this series in a computer program, we use floating point type values to store the partial sums. Floating point values are stored in fixedsize memory space, which means that they are often an approximation of an exact numeric value. In particular, very small and very large values may not be able to be stored exactly in a floating point number. As a result, your program’s summation of n terms of this series will reach 1.0 well before n reaches infinity.
2.1. Tips

Implementing and testing the iterative (nonrecursive version of the function) first is usually helpful—you then have a correct solution to which you can compare its return value to your recursive version’s return value.

Add some debug statements to your function to see what you are passing and what is returned from each recursive call. (and make sure to remove these before you submit)
2.2. Sample Output
Here is output from a couple runs of a working solution (note what the sum of the series is for odd and even values of n in this example):
$ python3 recursive_nums.py
First, try functions that compute the sum of the even numbers between 1 and n
enter a value for n: 10
The sum of the even numbers 0 to 10 computed iteratively is 30
The sum of the even numbers 0 to 10 computed recursively is 30
Next, let's try functions that sum a series
enter the number of terms, n, in the series to sum: 7
The sum of the series for 7 terms computed iteratively is 0.992188
The sum of the series for 7 terms computed recursively is 0.992188
$ python3 recursive_nums.py
First, try functions that compute the sum of the even numbers between 1 and n
enter a value for n: 11
The sum of the even numbers 0 to 11 computed iteratively is 30
The sum of the even numbers 0 to 11 computed recursively is 30
Next, let's try functions that sum a series
enter the number of terms, n, in the series to sum: 3
The sum of the series for 3 terms computed iteratively is 0.875000
The sum of the series for 3 terms computed recursively is 0.875000
3. Recursion on Strings
In the file recursive_strs.py
, implement an iterative
(count_lower_iterative(str)
and a recursive version
count_lower_recursive(str)
of a function that takes a string
and returns the number of lowercase alphabetic characters in
the string.
Your main
function should:

prompt the user to enter a string value and read it in (any input string is fine).

make calls to
count_lower_iterative(str)
andcount_lower_recursive(str)
and print out their return values (which should be the same)
Test your functions on different input strings to ensure that they work
correctly for different character values in the strings.
Some examples strings to test: "hello there"
, "Hello There"
,
"HELLO, THERE!"
, "12345678"
, ":)"
3.1. Tips

Use string slicing to create substrings to pass to recursive calls. See last week’s class notes for some examples.

Some other common string methods
3.2. Sample Output
Here is output from a couple example runs of a working program:
$ python3 recursive_strs.py
This program counts the number of lower case alpha characters in a string.
Enter a string value: HI THERE
The number of lower case characters in the string HI THERE
is 0 computed iteratively
is 0 computed recursively
$ python3 recursive_strs.py
This program counts the number of lower case alpha characters in a string.
Enter a string value: Hi ThERE
The number of lower case characters in the string Hi ThERE
is 2 computed iteratively
is 2 computed recursively
$ python3 recursive_strs.py
This program counts the number of lower case alpha characters in a string.
Enter a string value: HI, There!
the number of lower case characters in the string HI, There!
is 4 computed iteratively
is 4 computed recursively
4. Recursion on Lists
On Monday, the professors will talk some more about the inplace recursion on lists, which is required for this program. We will also briefly talk about running programs with command line arguments. The starting point code for this problem includes all the code needed to get the filename and float value from the command line arguments, but you should look at the example command lines and sample output to see some examples of how to run this program with command line arguments. 
In the file recursive_lists.py
, implement a recursive version of a
function that takes a list and a float value, and squares all the elements in
the list that are smaller than the value. Your function should also
return the total number of values in the list that were squared.
For this problem you do not need to also implement an iterative version, but you may if it is helpful with your debugging and testing.
Your program will be run with two command line arguments:

The first is the file name of a file of numbers that you will use to initialize the list of values.

The second is the float value, used to determine which values to square.
$ python3 recursive_lists.py numbers.txt 14.0
$ python3 recursive_lists.py /home/newhall/public/cs21/bignumbers.txt 3
$ python3 recursive_lists.py myfile.txt 10.4
The main
function is started for you. It gets the filename and the float
value from the two command line arguments. You should complete it to do the
following:

open the file whose name is given as the first command line argument, and read the values into a list of floats

print out the list of values (call the
print_list
function that is already implemented for you in this file) 
call your recursive function

prints out the number of values that were squared and the resulting list of values after the call (call the
print_list
function).
4.1. Requirements

For this program, you must do the recursion in place on the list. This means that you should not create new copies of full or partial lists to pass to each recursive call, but instead pass the list and the next index value to each recursive call. Your call from
main
to your recursive function should pass in either bucket number (index value 0) or the largest valid index value in the list (depending on in which direction you recurse on the list). 
You should create a test file in
myfile.txt
that is in the correct format for this program and try running your program with your test file too. And you are encouraged to create other test files to test your solution.
4.2. Input File Format
The file numbers.txt
has a list of floating point values, one per line. For
example, the first few lines look like the following:
% cat numbers.txt
8
8.4
23.4
55.2
100
...
You should also create your own file contents in myfile.txt
in this same
format and try out your program on this file as well.
4.3. Tips

Try implementing part of the recursive function first, and test it, and then add the second part. For example, first focus on squaring all the values in the list smaller than the passed value (don’t worry about the counting how many yet). When you get that to work, then add in the code to your recursive function to also recurisvely compute the count of the number of values that are squared (and make sure your function returns this value).

See last week’s class notes for more information about command line arguments.

Some common list methods

Some common file methods
4.4. Sample Output
Here is output from a couple runs of a working program:
% python3 recursive_lists.py numbers.txt 0
This program squares all the values in a list that are smaller than 0.00.
Here is the list:
8.00 8.40 23.40 55.20 100.00 300.00 20.00 0.45 2.90 100.60
13.50 101.20 0.45 12.90 10.16 135.00 112.00 135.00 11.20 99.00
There were 1 values in the list smaller than 0.0, here's the list now:
8.00 70.56 23.40 55.20 100.00 300.00 20.00 0.45 2.90 100.60
13.50 101.20 0.45 12.90 10.16 135.00 112.00 135.00 11.20 99.00
% python3 recursive_lists.py numbers.txt 13.6
This program squares all the values in a list that are smaller than 13.60.
Here is the list:
8.00 8.40 23.40 55.20 100.00 300.00 20.00 0.45 2.90 100.60
13.50 101.20 0.45 12.90 10.16 135.00 112.00 135.00 11.20 99.00
There were 9 values in the list smaller than 13.60, here's the list now:
64.00 70.56 23.40 55.20 100.00 300.00 20.00 0.20 8.41 100.60
182.25 101.20 0.20 166.41 103.23 135.00 112.00 135.00 125.44 99.00
$ python3 recursive_lists.py ~newhall/public/cs21/bignumbers.txt 20
This program squares all the values in a list thatare smaller than 20.00.
Here is the list:
14.10 30.90 33.50 19.10 9.00 93.00 80.50 0.80 30.40 54.50
13.40 22.10 78.00 34.20 4.30 79.80 19.20 97.00 13.90 55.60
...
(lots more values listed)
There were 97 values in the list smaller than 20.00, here's the list now:
198.81 30.90 33.50 364.81 81.00 93.00 80.50 0.64 30.40 54.50
179.56 22.10 78.00 34.20 18.49 79.80 368.64 97.00 193.21 55.60
...
(lots more values listed)
5. Extra Challenge
This is an optional extra challenge. This part does not affect your grade, so please only attempt this after completing the rest of your lab.
So far, we’ve only seen an iterative version of binary search. However, it also makes sense to define binary search recursively by repeatedly calling the same binary_search function with different inputs.
For this extra challenge, in extra_challenge.py
define a binary_search
function that takes in an item to search for, a list to search within, a low
index, and a high index. The function should return the index at which the item
appears in the list or 1 if the item does not appear in the list.
If the item appears in the list more than once, you can return the index of the first one you find — it doesn’t necessarily have to be the first index in the list where the item appears.
You may assume that the list is already sorted prior to calling your binary_search function.
Like the other programs for this week, write a main function with several test cases to verify that your implementation works as expected.
6. Answer the Questionnaire
Each lab will have a short questionnaire at the end. Please edit
the Questions11.txt
file in your cs21/labs/11
directory
and answer the questions in that file.
Once you’re done with that, you should run handin21
again.
Submitting lab assignments
Remember to run handin21
to turn in your lab files! You may run handin21
as many times as you want. Each time it will turn in any new work. We
recommend running handin21
after you complete each program or after you
complete significant work on any one program.
Logging out
When you’re done working in the lab, you should log out of the computer you’re using.
When Remotely logged in
When you are ssh’ed into the CS labs, first quit any applications you are
running, like vim
, then simply type exit
at the prompt in your terminal
window to disconnect.
When Physically logged in
When you are in a CS lab logged into a CS machine. First quit any applications you are running, like the browser and the terminal. Then click on the logout icon ( or ) and choose "log out".
If you plan to leave the lab for just a few minutes, you do not need to log out. It is, however, a good idea to lock your machine while you are gone. You can lock your screen by clicking on the lock icon. PLEASE do not leave a session locked for a long period of time. Power may go out, someone might reboot the machine, etc. You don’t want to lose any work!
Resources
Programming Tips
As you write programs, use good programming practices:

Use a comment at the top of the file to describe the purpose of the program (see example).

All programs should have a
main()
function (see example). 
Use variable names that describe the contents of the variables.

Write your programs incrementally and test them as you go. This is really crucial to success: don’t write lots of code and then test it all at once! Write a little code, make sure it works, then add some more and test it again.

Don’t assume that if your program passes the sample tests we provide that it is completely correct. Come up with your own test cases and verify that the program is producing the right output on them.

Avoid writing any lines of code that exceed 80 columns.

Always work in a terminal window that is 80 characters wide (resize it to be this wide)

In
vim
, at the bottom left in the window, there is an indication of both the line and the column of the cursor.

Function Comments
All functions should have a toplevel comment! Please see our function example page if you are confused about writing function comments.
Are your files in the correct place?
Make sure all programs are saved to your cs21/labs/11
directory! Files
outside that directory will not be graded.
$ update21 $ cd ~/cs21/labs/11 $ pwd /home/username/cs21/labs/11 $ ls Questions11.txt (should see your program files here)