Make sure all programs are saved to your cs21/labs/10 directory. Files outside this directory will not be graded.

Topics for this assignment

Overview

In the file recursion.py you will write a number of recursive function described below. After implementing your functions, you must write a main program that tests your functions for correctness.

1. Sorted

Write a recursive function isSorted(lst) that returns True if the provided input list lst is sorted and False otherwise. Your solution should be recursive and not use any loops.

isSorted([6,3,1,2]) # False
isSorted([1,7,10]) # True
isSorted([]) # True

2. Exceeds

Write a recursive function countExceeds(lst, val) that computes and returns the number of values in the input list lst that are strictly greater than the value val.

3. Remove letter

Write a recursive function removeLetter(txt, let) that removes all occurences of the letter let from the string txt and returns a new string with let removed.

removeLetter("qqqSqqquqrpqqqrqqqiqqqqqsqqqqeqq!q", "q") #Surprise!
removeLetter("Pittsburgh", "x") #Pittsburgh

4. Mirror

Write a recursive function mirror(text) that takes an string text as input and returns a new string that contains the original text and a mirrored copy. For example mirror("kayak ") should return "kayak kayak" (note the trailing space in the input and the double space in the output). Some other examples are below.

5. Ruler

Write a recursive function ruler(n) that prints a vertical ruler pattern of dashes. The middle of the pattern should be a row of n dashes, with a row of n-1 dashes in the middle of the top and bottom halves of the pattern, for an integer input n > 0. The ruler should continue to be subdivided until the smallest section is labeled by a single dash. Some examples are shown below.

Testing

Write a main program that tests all your recursive functions. You must have at least three tests for each function excluding any of the tests above. You are welcome to use the tests above, but you must add at least three extra for each function.

Requirements/Hints

All your solutions to the five functions must be recursive. You cannot use loops in any of these five functions. You can use loops in your tests/main if needed. You will need one or more base cases for each function. If a function is supposed to return a value, make sure all possible paths, including recursive cases and base cases return a value.

The online Python Tutor may be helpful for tracing/debugging your recursive solutions. The online tutor will allow you to post code samples and step through the execution of your program. It will show program output and the stack diagram. Caution: Python tutor draws the stack differently than we have instructed you to draw stacks for quizzes and homeworks. In particular, python tutor draws the stack going down instead of up. While we are providing a link to this tool as a potential benefit, you should still draw stacks as instructed in class.

Submit

Once you are satisfied with your programs, fill out the questionnaire in QUESTIONS-10.txt. Then run handin21 a final time to make sure we have access to the most recent versions of your file.

CS21 Lab 10: Recursion

Due Saturday night, April 20