Using Recursion

For this assignment you are going to write code that solves problems using recursion. Note the emphasis: you must use recursion!

If you're having problems starting a question, consider the simplest possible case (ie, a '1' or a single-character string, etc) and using induction, figure out how to get to the next case.

All questions in this assignment will be answered in the same Python file: assign2.py. Read the description of each question below, and refer to the assign2.py file comments for further clarification.

Pay close attention to the specifications and the submission requirements.

1. Permutations [20%]

In the assign2.py file, you will modify the recursive function called permutations(), which is given on slide 17 of Topic 2 class notes (refer to that slide for further explanation). The current code outputs the permutations as in the first version on slide 18. You must modify the code so that the output is in a more 'systematic' ordering, as in the second version on slide 18.

2. Generating Strings [40%]

In the assign2.py file, implement the recursive function called generateReverseOrder(), which generates all length-n strings of 0s and 1s, for a given non-negative integer n, in order from largest to smallest (aka, descending order).

Your function must have n as the only parameter and must return a list containing all length-n strings of 0s and 1s (in the correct order).

Run the code to get an idea of what the expected output should look like.

Note: The test output examples are in descending order, since if you consider them as binary numbers, they start at 2ⁿ-1 and decrement each time.

3. Analyzing a String [40%]

In the assign2.py file, implement the recursive function called countChars(), which analyzes the given string and returns a 3-element list of integers representing the number of consonants, vowels, and other characters (respectively) in that string.

Your function must have a string s as the first parameter; you may add other parameters as necessary.

Sample output should be as follows:

s = "abc de"  Consonants, Vowels, Other: [3, 2, 1] 

s = "To be or not to be"  Consonants, Vowels, Other: [7, 6, 5] 

Submission Information

Submit the assign2.py file which contains the solutions (and tester code) for all three questions above.

Make sure you do not touch the parts of code in the file where you are told not to do any modifications. You will receive 0% on the question if you do so.

Do not submit any other files or documentation; they will not be used or assessed.

After submission, check that all your files are present and correct!

The D2L/Brightspace Dropbox has been set up to allow you to submit updates to your assignment multiple times until the due date/time.

Prepared By: Department of Computer Science, MUN (BE230121)