CS21 Lab 10: Recursion

Due Saturday, April 15 by 11:59pm

  • Part 1 turned in at the start of class on April 14, on paper

  • Part 2 turned in using handin21

Goals

The goals for this lab assignment are:

  • Trace recursive functions.

  • Design recursive functions and develop your understanding of recursion using comparisons to iterative functions.

  • Identify base and recursive cases.

1. Written assignment: Tracing Stack Diagrams

The first part of this lab is a written assignment to trace through some Python code, show the program output and draw the stack. Download the following .pdf file and print it out: lab10stack.pdf

You should draw your solution on the printout, and submit it at the start of class on Friday.

2. Designing Recursive Functions

When designing recursive programs, the first step is to identify the base case(s) first: the simplest case where there is not a recursive call. Then move on to the recursive case(s). Your recursive functions should not use any for or while loops.

Requirements

  • Your iterative functions on this lab are allowed to use for or while loops.

  • Your recursive functions on this lab should not use any for or while loops.

Tips

  • Implementing and testing the iterative (non-recursive) version of a function first is helpful. You then have a correct solution that you can use to compare return values with your recursive version’s return value.

  • Add debugging statements to your function so that you can see what is getting passed and returned from each recursive call. (Make sure to remove these before your final submission.)

Helpful syntax reminders

When working through these recursion problems, we’ll frequently be using strings and lists, which are both "collections" of things: strings are collections of characters, and lists are collections of arbitrary elements. As collections, both strings and lists offer some utilities to make it easier to work with them. We’ve seen these before, but they’ll come in handy for this lab, so here’s a brief refresher:

Concatenation (+ operator)

Strings and lists both support using the + operator for concatenation:

>>> s1 = "hello"
>>> s2 = "there"
>>> s1 + s2
'hellothere'

>>> l1 = [1, 2]
>>> l2 = [3, 4]
>>> l1 + l2
[1, 2, 3, 4]

Note that when concatenating collections, the values on both sides of the + operator must be of the same type (e.g., both strings or both lists). If you attempt to use + on different types, you might see a message like:

>>> s1 = "hello"
>>> l1 = [1, 2]
>>> s1 + l1
Traceback (most recent call last):
  File "", line 1, in 
TypeError: can only concatenate str (not "list") to str
Slicing

Both strings and lists support slicing, which allows you to access subsets of the string/list. When slicing a collection, you can express a range of indices from which to pull a subset of the collection. For example:

>>> s = "hello CS21"
>>> s[2:5]
'llo'

Here, the [2:5] says to extract from s the characters starting at index 2 up to (but not including) index 5. The same syntax works for lists:

>>> l = ["a", "b", "c", "d", "e", "f"]
>>> l[1:4]
['b', 'c', 'd']

For this lab, you may find that occasionally, you want to slice a collection to take all items starting from a certain index. Python supports a shorthand syntax to get all remaining items in the collection starting from an index:

>>> l = ["a", "b", "c", "d", "e", "f"]
>>> l[2:]
['c', 'd', 'e', 'f']

With this shorthand syntax, you don’t need to worry about how many items are in the collection if you just want to peel off item(s) from the front.

2.1. Recursion on numbers: sum of odd numbers

  1. In the file math-functions.py, write an iterative (not recursive) function iterative_odd_sum(n) which takes one parameter, n, and iteratively computes the sum of all the odd numbers up to n, returning the result. You may assume that the user will pass a nonnegative integer (you don’t need to worry about checking for bad input).

    For example:

    iterative_odd_sum(5) = 1 + 3 + 5 = 9
iterative_odd_sum(6) = 1 + 3 + 5 = 9
iterative_odd_sum(2) = 1
iterative_odd_sum(0) = 0

  2. Write some code in main() to test this function on different values of n.

  3. Next, write a recursive function recursive_odd_sum(n).

  4. Add some more tests in main().

Sample output

Here is output from a few runs of a working solution.

Now testing the odd sum functions.
The sum of the odd numbers up to 78 is:
  1521 computed iteratively.
  1521 computed recursively.
The sum of the odd numbers up to 7 is:
  16 computed iteratively.
  16 computed recursively.
The sum of the odd numbers up to 57 is:
  841 computed iteratively.
  841 computed recursively.
The sum of the odd numbers up to 58 is:
  841 computed iteratively.
  841 computed recursively.
The sum of the odd numbers up to 29 is:
  225 computed iteratively.
  225 computed recursively.

2.2. Recursion on lists: sum of positive numbers

  1. Again in the file math-functions.py, write an iterative (not recursive) function iterative_sum_of_positive(lst) which takes one parameter (a list of integers lst), and iteratively computes the sum of all the positive numbers in lst, returning the result. You may assume that the user will pass a list containing only integers (you don’t need to worry about checking for bad input).

    For example:

    iterative_sum_of_positive([-3, 7, 8, -120]) = 15
iterative_sum_of_positive([]) = 0
iterative_sum_of_positive([0, -1, -12, 14, 73, 20]) = 107
iterative_sum_of_positive([-6, -19, -42, -32]) = 0

  2. Write some code in main() to test this function on different lists.

  3. Next, write a recursive function recursive_sum_of_positive(n).

  4. Add some more tests in main(). (Note that your main() should contain tests from the sum of odd numbers problem, as well!)

Sample output

Here is output from a few runs of a working solution.

Now testing the sum of positive numbers functions.
The list is: [70, -75, -1, -41, 34]
  The sum of the positive numbers in that list is:
    104 computed iteratively.
    104 computed recursively.
The list is: [-61, 6, 84, 10, 32, 77]
  The sum of the positive numbers in that list is:
    209 computed iteratively.
    209 computed recursively.
The list is: []
  The sum of the positive numbers in that list is:
    0 computed iteratively.
    0 computed recursively.
The list is: [-28, -79, 26]
  The sum of the positive numbers in that list is:
    26 computed iteratively.
    26 computed recursively.
The list is: [73, -97, -71]
  The sum of the positive numbers in that list is:
    73 computed iteratively.
    73 computed recursively.

2.3. Recursion on strings: disemvowelling again!

In the file vowels.py, write a recursive function called recursive_disemvowel that takes a string as a parameter and returns a new string with all the vowels removed. (You may want to refer to your lab 3 solution for an iterative approach to this problem.)

def recursive_disemvowel(s):
   """ return a version of string s, with all vowels removed """

You should include some test cases in main(). Sample output is below, but you should think up some of your own test cases and make sure that your function always works.

Sample output

Here is output from a few runs of a working solution.

"Swarthmore" becomes "Swrthmr" when disemvowelled.
"computer science" becomes "cmptr scnc" when disemvowelled.
"playing card" becomes "plng crd" when disemvowelled.
"recursion is the best!" becomes "rcrsn s th bst!" when disemvowelled.
"" becomes "" when disemvowelled.
"woW this is 1000 times cooler than iteration" becomes "wW ths s 1000 tms clr thn trtn" when disemvowelled.

If you want your print statements to include double quotes, you can write your print statement as a string in single quotes:

>>> x = "Swarthmore"
>>> y = "Swrthmr"
>>> print('"%s" becomes "%s" when disemvowelled.' % (x,y))
"Swarthmore" becomes "Swrthmr" when disemvowelled.

2.4. Optional 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.

In the file ruler.py, add a recursive function ruler and a main function.

Using the Zelle graphics library, RECURSIVELY draw the marks that you might find on a ruler. For example: ruler

Your function should take only three input parameters:

  • the X-coordinate of the center line

  • the height of the center line

  • a graphics window in which to draw the markings

Keep in mind that the ruler we are drawing is twice as wide as it is tall. The center line in the example ruler is half as tall as the window.

As with the other programs for this week, your main should test your ruler implementation. For example, can you draw rulers of different sizes? What if the window size changes? (Keep in mind that the size will always need to preserve the "twice as wide as tall" aspect ratio.)