HW 11 (Recursion)

Assignment overview

You'll practice writing and testing recursive functions.

Logistics

This is an individual assignment. You are welcome to discuss any part of the assignment with classmates, course staff or Anna. Make sure to cite any help you receive in the "acknowlegdements" portion of the assignment.

This assignment is due at 10PM on Wednesday, May 27.

Setup

Mount the COURSES drive and create a folder called hw11 in your STUWORK folder. Open the new folder in VSCode. If you need a refresher on how to complete these steps, refer back to the in-class lab from the first day of class.

Create a new file called recursion.py in your hw11 folder.

Task 1: replace double letters

You will write a function called replaceDoubleLetters that accepts a string of lowercase letters as a parameter. (It's fine to assume in writing the code and in testing that this input string is all lowercase letters.) This function should return a new string where all double letter pairs (when reading left-to-right) have been replaced with a single capital letter. For example, 

> replaceDoubleLetters("butter")
"buTer"
> replaceDoubleLetters("goodpizza")
"gOdpiZa"
> replaceDoubleLetters("caaarleton")
"cAarleton"

Do not use string methods (e.g., replace): instead, use string indexing, slicing, and concatenation. Your program should be recursive and should not contain any loops.

Testing your code

Create a main function and add the if __name__ == "main" block (look back at previous assignments if you're unsure about the syntax). Inside the main function, add at least 3 test cases that are different than the ones I've written here. For instance, I might write the test case 

result1 = replaceDoubleLetters("butter")
print("Expected result: buTer, actual result:", result1)

Try to come up with test cases that cover a variety of examples, so that you are convinced that your code works for all valid inputs.

Task 2: permutations

You will write a function called permutations that accepts a string and returns a list containing all permutations of the characters in that string. For example, 

> permutations("abc")
["abc", "acb", "bac", "bca", "cab", "cba"]

You may assume that each character in the input string is unique. The order of the permutations in the list you return does not matter.

Unlike for the replaceDoubleLetters function, you can use loops in permutations (and will probably not be able to solve the problem without them). However, the core of the problem needs to be solved with recursion.

Hint: to figure out the recursive case I recommend using a concrete example. Assume your code works correctly for smaller strings, e.g., that permutations("bc") returns ["bc", "cb"]. How would you use this result to build the list of all permutations of "abc"?

Testing your code

Add at least 3 test cases to your main function. Try to include a range of cases that will convince you, and me, that your code works correctly.

Wrap up

When you're finished, make sure to complete the usual documentation steps. This includes adding comments, writing function docstrings, and adding a top-level comment, acknowledgements, and a reflection to the header.

You should also think about coding style. Have you written everything in a consistent way that is easy to read? Does your code have any unnecessary print statements? (Remove them.) Is there any repetitive code that could be rewritten to use loops or helper functions? Review the style document on Moodle for the expectations for this assignment.

Assignment submission and misc. notes

Handing in the assignment

You need to hand in recursion.py on Gradescope.

Grading

This assignment is worth 20 points, broken up as follows:

  • 7 points: replaceDoubleLetters
  • 8 points: permutations
  • 2 points: there is code in main to test each of the functions
  • 3 points: style (reflections, acknowledgments, docstrings/comments, style)

Start early, ask lots of questions, and have fun!

Anna's acknowledgements

This assignment was adapted from Anna Rafferty's and Layla Oesper's teaching materials. Thanks for sharing!