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:

  1. Compute the Sum of the Even numbers from 1 to n. Implement the functions sum_of_evens_iter(n) and sum_of_evens_recursive(n) that take an integer input value n and return the sum of all the even numbers between 1 and n inclusive.

    Create some test cases to test the correctness of these functions, calling them from main.

  2. 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) and sum_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 fixed-size 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 (non-recursive 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) and count_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

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 in-place 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:

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

  2. 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:

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

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

  3. call your recursive function

  4. 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 Questions-11.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 (logout icon or other logout icon) 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 xlock 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 top-level 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
Questions-11.txt
(should see your program files here)