Recursive Functions in Python - Assignment Sample for University Students

Unlock the power of recursion with our detailed presentation on Recursive Functions in Python, tailored specifically for students and programming enthusiasts! Dive into the concept of recursion, understand its mechanics, and learn how to implement effective recursive solutions to complex problems.

This Assignment Sample includes:

A thorough explanation of recursion and its principles
Step-by-step examples of recursive functions in Python
Common use cases and practical applications
Tips and best practices for writing efficient recursive code
Detailed solutions to a sample Python assignment on recursion
Whether you are a beginner looking to grasp the basics or an advanced learner aiming to refine your skills, this presentation is designed to enhance your understanding and proficiency in using recursive functions in Python.

Visit ProgrammingAssignmentHelper.com for more tutorials, assignment help, and resources to support your programming journey.

1. Recursive Functions in Python Assignment Sample for University Students For any Assignment related queries, Call us at : - [phone] You can mail us at : - [email protected] or Reach us at : - https://www.programmingassignmenthelper.com/

2. Introduction Brief introduction to the topic of recursive functions in Python. Importance of understanding recursion in computer science. Overview of what the assignment will cover. Learning Objectives Understand the concept of recursion. Learn how to implement recursive functions in Python. Apply recursion to solve common programming problems. Develop problem-solving and critical thinking skills. What is Recursion? Recursion is a method of solving problems where a function calls itself as a subroutine. Key Characteristics: Base Case: The condition under which the function stops calling itself. Recursive Case: The condition under which the function continues to call itself.

3. This problem set has two parts. The first part allows you to practice thinking about problems in a recursive fashion, taking advantage of the idea that one can reduce the problem to a simpler version of the same problem. In ps4a.py , you will write a recursive function that takes as input a string and figures out all the possible reorderings of the characters in the string. The second part will give you experience in thinking about problems in terms of classes, each instance of which contains specific attributes as well as methods for manipulating them. In ps4b.py , you will use object-oriented programming to write a Caesar/shif t cipher. In ps4c.p y , y o u wil l u s e objec t- orient ed pr og ra mm i ng t o write a very simple substitution cipher. As always, please do not rename the files we provide you with, change any of the provided helper functions, change function/method names, or delete provided docstrings . Yo u wil l n e ed t o keep words.tx t and story . tx t i n t he sa me f olde r in which you store ps4a.py, ps4b.py and ps4c.py .

4. Part A: Permutations of a string A permutation is simply a name for a reordering. So the permutations of the string ‘ abc ’ are ‘ abc ’, ‘ acb ’, ‘ bac ’, ‘ bca ’, ‘cab’, and ‘ cba ’. Note that a sequence is a permutation of itself (the trivial permutation). For this part of the pset you’ll need to write a recursive function get_permutations that takes a string and returns a list of all its permutations. You will find this function helpful later in the pset for part C. A couple of notes on the requirements: Recursion MUST be used , global variables may NOT be used. Additionally, it is okay to use loops to code the solution. The order of the returned permutations does not matter. Please also avoid returning duplicates in your final list.

5. -- for this approach, our base case is if sequence is a single character (there’s only one way to order a single character). If sequence is longer than one character, we need to identify a simpler version of th e proble m that , i f s o lved , wil l help us ea sil y find all pe r mu ta tions f o r sequenc e . The pseudocode below gives one approach to recursively solving this problem. Give n an inpu t string sequenc e : Base case: if sequence is a single character, there’s only one way to order it return a singleton list containing sequence Recursive case: suppose we have a method that can give us a list of all permutations of all but the first character in sequence then the permutations of all characters in sequence would be all the different ways we can insert the first character into each permutation of the remaining characters

6. example : if our word was ‘bust’, we hold out the character ‘b’ and get the list [‘ ust ’, ‘ sut ’, ‘ stu ’, ‘ uts’ , ‘ tus ’, ‘ tsu ’] then ‘ ust ’ gives us: ‘ b ust’, ‘ u b st ’, ‘ us b t ’, ‘ ust b ’ ‘ sut ’ gives us: ‘ b sut ’, ‘ s b ut ’, ‘ su b t ’, ‘ sut b ’ and so on … Part B: Cipher Like Caesar Ever want to relive the glory days of your youth and pass secret messages to your friends? Well, here is your chance! But first, here is some vocabulary: Encryption - the process of obscuring or encoding messages to make them unreadable Decryption - making encrypted messages readable again by decoding them Cipher - algorithm for performing encryption and decryption Plaintext - the original message Ciphertext - the encrypted message. Note: a ciphertext still contains all of the original message information, even if it looks like gibberish.

7. Caesar Cipher The idea of the Caesar Cipher is to pick an integer and shift every letter of your message by that integer. In other words, suppose the shift is k . Then, all instances of the i th letter of the alphabet that appear in the plaintext should become the ( i + k ) th letter of the alphabet in the ciphertext . You will need to be careful with the case in which i + k > 26 (the length of the alphabet). We will treat uppercase and lowercase letters individually, so that uppercase letters are always mapped to an uppercase letter, and lowercase letters are always mapped to a lowercase letter. If an uppercase letter maps to “A”, then the same lowercase letter should map to “a”. Punctuation and spaces should be retained and not changed. For example, a plaintext message with a comma should have a corresponding ciphertext with a comma in the same position. Classes and Inheritance This is your first experience coding with classes! Get excited

8. ! We will have a Messag e class wit h t w o s ub clas ses PlaintextMessag e a nd CiphertextMessag e . Message contains methods that could be used to apply a cipher to a string, either to encrypt or to decrypt a message (since for Caesar codes this is the same action). PlaintextMessage has methods to encode a string using a specified shift value; our class will always create an encoded version of the message, and will have methods for changing the encoding. CiphertextMessage contains a method used to decode a string. When you have completed your implementation, you can either create a CiphertextMessage instance using an encrypted string that someone provides you and try to decrypt it; or you can encrypt your own PlaintextMessage instance, then create a Ciphert extMessage instance from the encrypted message within the PlaintextMessage instance, and try to decrypt it and see if it matches the original plaintext message.

9. Don’t overthink this; a getter method should just return an attribute and a set method should just set an attribute equal to the argument passed in. Although they seem simple, we need these methods in order to make sure that we are not manipulating attributes we shouldn’t be. Directly using class attributes outside of the class itself instead of using getters and setters will result in a point deduction – and more importantly can cause you headaches as you design and implement object class hierarchies. Rules You do not have to use recursion in Part B, but you are welcome to. There are a couple of helper functions that we have implemented for you: load_words and is_word . You may use these in your solution and you do not need to understand them completely, but should read the associated comments. You should read and understand the helper code in the rest of the file and use it to guide your solution. Part 1: Message

10. Fill i n th e methods of t he Messag e clas s f o und i n ps4b.p y a cco rdin g t o t he specifications in the docstrings We have provided skeleton code in the Message class for the following functions - your task is to implement them. Please see the docstring comment with each function for more information about the function specification. init (self, text) The getter methods get_message_text (self) Note: This should return an immutable version of the message text we added to this object in init. Luckily, strings are already immutable objects, so we can simply return that string. get_valid_words (self) Note: this should return a COPY of self.valid_words to prevent someone from accidentally mutating the original list. build_shift_dict (self, shift) Note : you may find t he strin g m odule’ s ascii_lowercas e con s t a nt helpful here.

11. apply_shift (self, shift) Hint: use build_shift_dict (self, shift). Remember that spaces and punctuation should not be changed by the cipher. Part 2: PlaintextMessage Fill in the methods of the PlaintextMessage class found in ps4b.py according to the specifications in the docstrings . The methods you should fill in are: init (self, text, shift) Use the parent class constructor to make your code more concise. Take a look at Style Guide #7 if you are confused. The getter methods get_shift (self) get_encryption_dict (self) Note: this should return a COPY of self.encryption_dict to prevent someone from mutating the original dictionary.

12. get_message_text_encrypted (self) change_shift (self, shift) Hint: think about what other methods you can use to make this easier. It shouldn’t take more than a couple lines of code Part 3: CiphertextMessage Don’t you want to know what your friends are saying? Given an encrypted message, if you know the shift used to encode the message, decoding it is trivial. If message is the encrypted message, and s is the shift used to encrypt the message, then apply_shift (message, 26-s) gives you the original plaintext message. Do you see why? The problem, of course, is that you don’t know the shift. But our encryption method only has 26 distinct possible values for the shift! We know English is the main language of these emails, so if we can write a program that tries each shift and maximizes the number of English words in the decoded message, we can decrypt their cipher!

13. Fill in the methods of the CiphertextMessage class found in ps4b.py according to the specifications in the docstrings . The methods you should fill in are: init (self, text) Hint: use the parent class constructor to make your code more concise. Take a look at Style Guide #7 if you are confused. decrypt_message (self) Note: is_word will ignore punctuation and other special characters when considering whether a word is valid. Part 4: Testing Write two test cases for PlaintextMessage and two test cases for CiphertextMessag e i n c ommen t s under i f name = = ‘ main ’ . Ea ch test case should display the input, expected output, and actual output. An example can b e found i n ps4b.p y .

14. Then , dec ode t he f il e s to r y . txt a nd write the best shift value used to decrypt the story, and unencrypted story in a comment underneath your test cases. Part C: Substitution Cipher A better way to hide your messages is to use a substitution cipher. In this approach, you create a hidden coding scheme, in which you substitute a randomly selected letter for each original letter. For the letter “a”, you could pick any of the other 26 letters (including keeping “a”), for the letter “b”, you could then pick any of the remaining 25 letters (other than what you selected for “a”) and so on. You can probably see that the number of possibilities to test if you wanted to decrypt a substitution ciphered message is much larger than for a Caesar cipher (26! compared to 26). So for this problem, we are going to just consider substitution ciphers in which the vowels are encrypted, with lowercase and uppercase versions of a letter being mapped to corresponding letters. (For example, ‘A’ -> ‘O’ then ‘a’->’o’).

15. Classes and Inheritance Similar to the Caesar cipher, we are going to use classes to explore this idea. We will have a SubMessage class with general functions for handling Substitution Messages of this kind. We will also write a class with a more specific implementation and specification, EncryptedSubMessage , that inherits from the SubMessage class. Your job will be to fill methods for both classes according to the specifications given in the docstrings of ps4c.py . Please remember that you never want to directly access attributes outside a class - that’s why you have getter and setter methods. Again, don’t overthink this; a get method should just return a variable and a set method should just set an attribute equal to the parameter passed in. Although they are simple, we need these methods in order to make sure that we are not manipulating attributes we shouldn’t be. Directly using class attributes outside of the class itself instead of using getters and setters will result in a point deduction – and more importantly can cause you headaches as you design and implement object class hierarchies.

16. Part 1: SubMessage Fill in the methods of the SubMessage class found in ps4c.py according to the specifications in the docstrings . We have provided skeleton code for the following methods in the SubMessage class - your task is to implement them init (self, text) The getter methods get_message_text (self) get_valid_words (self) Note: this should return a COPY of self.valid_words to prevent someone from mutating the original list. build_transpose_dict (self, vowels_permutation ) apply_transpose (self, transpose_dict ) Note: Pay close attention to the input specification when testing. Part 2: EncryptedSubMessage

17. init (self, text) The getter methods get_message_text (self) get_valid_words (self) Note: this should return a COPY of self.valid_words to prevent someone from mutating the original list. build_transpose_dict (self, vowels_permutation ) apply_transpose (self, transpose_dict ) Note: Pay close attention to the input specification when testing. Part 2: EncryptedSubMessage Fill in the methods of the EncryptedSubMessage class found in ps4c.py according to the specifications in the docstrings . Don’t you want to know what your friends are saying? Given an encrypted message, if you know the substitution used to encode the message, decoding it is trivial. You could just replace each letter with the correct, decoded letter.

18. Even if we keep all the consonants the same, we still have a lot of options for trying different substitutions for the vowels. As with the Caesar cipher, we can use the trick of testing (giving a proposed substitution) to see if the decoded words are real English words. We then keep the decryption that yields the most valid English words. Note that we have provided constants containing the values of the uppercase vowels, lowercase vowels, uppercase consonants, and lowercase consonants, for your convenience. In this part, you can use your get_permutations method from part A (it is already imported for you in the beginning of ps4c.py). The methods you should fill in are: init (self, text) Hint: use the parent class constructor to make your code more concise. Take a look at Style Guide #7 if you are confused. decrypt_message (self) Part 3: Testing

19. Write two test cases for SubMessage and two test cases for EncryptedSubMessag e i n c ommen t s under i f name = = ‘ main ’ . Each test case should contain the input, expected output, function call used, and actual output. Part A: Permutations of a String In this part, you are required to write a recursive function get_permutations that takes a string and returns a list of all its permutations. Here's how you can implement it: def get_permutations (sequence): """ Enumerate all permutations of a given string sequence (string): an arbitrary string to permute. Assume that it is a non-empty string. You MUST use recursion for this part. Non-recursive solutions will not be accepted. Returns: a list of all permutations of sequence

20. Example: >>> get_permutations (' abc ') [' abc ', ' acb ', ' bac ', ' bca ', 'cab', ' cba '] """ # Base case if len (sequence) == 1: return [sequence] # Recursive case permutations = [] first_char = sequence[0] rest_permutations = get_permutations (sequence[1:]) for perm in rest_permutations : for i in range( len (perm) + 1): new_permutation = perm[: i ] + first_char + perm[ i :] permutations.append ( new_permutation ) return permutations

21. # Test cases if __name__ == '__main__': test_cases = [ (' abc ', [' abc ', ' acb ', ' bac ', ' bca ', 'cab', ' cba ']), ('a', ['a']), (' ab ', [' ab ', ' ba ']), ] for sequence, expected in test_cases : result = get_permutations (sequence) print( f"Input : {sequence}\ nExpected Output: {expected}\ nActual Output: {result}\n") Part B: Caesar Cipher In this part, you need to implement a Caesar cipher using object-oriented programming. You will create a Message class and two subclasses PlaintextMessage and CiphertextMessage . import string ### Helper code ### def load_words ( file_name ):

22. ''' file_name (string): the name of the file containing the list of words to load Returns: a list of valid words. Words are strings of lowercase letters. Depending on the size of the word list, this function may take a while to finish. ''' # inFile : file inFile = open( file_name , 'r') # line: string line = inFile.readline () # wordlist: list of strings wordlist = line.split () return wordlist def is_word ( word_list , word): """ Determines if word is a valid word, ignoring capitalization and punctuation word_list (list): list of words in the dictionary. word (string): a possible word.

23. Returns: True if word is in word_list , False otherwise Example: >>> is_word ( word_list , 'bat') returns True >>> is_word ( word_list , ' asdf ') returns False """ word = word.lower () word = word.strip (" !@#$%^&*()-_+={}[]|\:;'<>?,./\"") return word in word_list WORDLIST_FILENAME = 'words.txt' ### Helper code ends ### class Message: def __init__(self, text): ''' Initializes a Message object text (string): the message's text

24. a Message object has two attributes: self.message_text (string, determined by input text) self.valid_words (list, determined using helper function load_words ) ''' self.message_text = text self.valid_words = load_words (WORDLIST_FILENAME) def get_message_text (self): ''' Used to safely access self.message_text outside of the class Returns: self.message_text ''' return self.message_text def get_valid_words (self): ''' Used to safely access a copy of self.valid_words outside of the class Returns: a COPY of self.valid_words ''‘ return self.valid_words [:]

25. def build_shift_dict (self, shift): ''' Creates a dictionary that can be used to apply a cipher to a letter. The dictionary maps every uppercase and lowercase letter to a character shifted down the alphabet by the input shift. The dictionary should have 52 keys of all the uppercase letters and all the lowercase letters only. shift (integer): the amount by which to shift every letter of the alphabet. 0 <= shift < 26 Returns: a dictionary mapping a letter (string) to another letter (string). ''' shift_dict = {} lowercase = string.ascii_lowercase uppercase = string.ascii_uppercase for i in range( len (lowercase)): shift_dict [lowercase[ i ]] = lowercase[( i + shift) % 26] shift_dict [uppercase[ i ]] = uppercase[( i + shift) % 26]

26. return shift_dict def apply_shift (self, shift): ''' Applies the Caesar Cipher to self.message_text with the input shift. Creates a new string that is self.message_text shifted down the alphabet by some number of characters determined by the input shift shift (integer): the shift with which to encrypt the message. 0 <= shift < 26 Returns: the message text (string) in which every character is shifted down the alphabet by the input shift ''' shift_dict = self.build_shift_dict (shift) encrypted_message = '' for char in self.message_text : if char in shift_dict : encrypted_message += shift_dict [char] else: encrypted_message += char

27. return encrypted_message class PlaintextMessage (Message): def __init__(self, text, shift): ''' Initializes a PlaintextMessage object text (string): the message's text shift (integer): the shift associated with this message A PlaintextMessage object inherits from Message and has five attributes: self.message_text (string, determined by input text) self.valid_words (list, determined using helper function load_words ) self.shift (integer, determined by input shift) self.encryption_dict (dictionary, built using shift) self.message_text_encrypted (string, created using shift)

28. self.message_text_encrypted = self.apply_shift (shift) def get_shift (self): ''' Used to safely access self.shift outside of the class Returns: self.shift ''' return self.shift def get_encryption_dict (self): ''' Used to safely access a copy of self.encryption_dict outside of the class Returns: a COPY of self.encryption_dict ''' return self.encryption_dict.copy () def get_message_text_encrypted (self): ''' Used to safely access self.message_text_encrypted outside of the class

29. Returns: self.message_text_encrypted ''' return self.message_text_encrypted def change_shift (self, shift): ''' Changes self.shift of the PlaintextMessage and updates other attributes determined by shift (i.e. self.encryption_dict and message_text_encrypted ). shift (integer): the new shift that should be associated with this message. 0 <= shift < 26 Returns: nothing ''' self.shift = shift self.encryption_dict = self.build_shift_dict (shift) self.message_text_encrypted = self.apply_shift (shift) class CiphertextMessage (Message): def __init__(self, text): '''

30. Initializes a CiphertextMessage object text (string): the message's text a CiphertextMessage object has two attributes: self.message_text (string, determined by input text) self.valid_words (list, determined using helper function load_words ) ''' super().__init__(text) def decrypt_message (self): ''' Decrypt self.message_text by trying every possible shift value and find the "best" one. We will define "best" as the shift that creates the maximum number of real words when we use apply_shift (shift) on the message text. If s is the original shift value used to encrypt the message, then we would expect 26 - s to be the best shift value for decrypting it.

31. Returns: a tuple of the best shift value used to decrypt the message and the decrypted message text using that shift value ''' max_valid_words = 0 best_shift = 0 best_decryption = '' for shift in range(26): decrypted_message = self.apply_shift (26 - shift) words = decrypted_message.split () valid_word_count = sum( is_word ( self.valid_words , word) for word in words) if valid_word_count > max_valid_words : max_valid_words = valid_word_count best_shift = 26 - shift best_decryption = decrypted_message return ( best_shift , best_decryption ) # Test cases if __name__ == '__main__':

32. # Test cases for PlaintextMessage plaintext1 = PlaintextMessage ('hello', 2) print( f"Input : hello\ nExpected Output: jgnnq \ nActual Output: {plaintext1.get_message_text_encrypted()}\n") plaintext2 = PlaintextMessage ('world', 5) print( f"Input : world\ nExpected Output: btwqi \ nActual Output: {plaintext2.get_message_text_encrypted()}\n") # Test cases for CiphertextMessage ciphertext1 = CiphertextMessage (' jgnnq ') print( f"Input : jgnnq \ nExpected Output: (24, hello)\ nActual Output: {ciphertext1.decrypt_message()}\n") ciphertext2 = CiphertextMessage (' btwqi ') print( f"Input : btwqi \ nExpected Output: (21, world)\ nActual Output: {ciphertext2.decrypt_message()}\n") # Decrypt the story story_string = get_story_string () cipher_story = CiphertextMessage ( story_string ) best_shift , decrypted_story = cipher_story.decrypt_message () print( f"Best shift value: { best_shift }\ nDecrypted story: { decrypted_story }")

33. Part C: Substitution Cipher In this part, you will implement a simple substitution cipher where only vowels are substituted. import string from ps4a import get_permutations class SubMessage : def __init__(self, text): ''' Initializes a SubMessage object text (string): the message's text a SubMessage object has two attributes: self.message_text (string, determined by input text) self.valid_words (list, determined using helper function load_words ) ''' self.message_text = text self.valid_words = load_words (WORDLIST_FILENAME)

34. def get_message_text (self): ''' Used to safely access self.message_text outside of the class Returns: self.message_text ''' return self.message_text def get_valid_words (self): ''' Used to safely access a copy of self.valid_words outside of the class Returns: a COPY of self.valid_words ''' return self.valid_words [:] def build_transpose_dict (self, vowels_permutation ): ''' Creates a dictionary that can be used to apply a cipher to a letter.

35. characters in vowels_permutation , and consonants remain the same. vowels_permutation (string): a string containing a permutation of vowels (a, e, i , o, u). The first letter in this string corresponds to the vowel 'a', this second to the vowel 'e', and so on in order. Returns: a dictionary mapping a letter (string) to another letter (string). ''' vowels = ' aeiou ' vowels_upper = 'AEIOU' transpose_dict = {} for i in range(5): transpose_dict [vowels[ i ]] = vowels_permutation [ i ] transpose_dict [ vowels_upper [ i ]] = vowels_permutation.upper ()[ i ] for letter in string.ascii_letters : if letter not in transpose_dict : transpose_dict [letter] = letter

36. return transpose_dict def apply_transpose (self, transpose_dict ): ''' Applies the substitution cipher to self.message_text with the input transpose_dict Creates a new string that is self.message_text encrypted by the dictionary transpose_dict (dictionary): a transpose dictionary Returns: the encrypted message text (string) ''' encrypted_message = '' for char in self.message_text : if char in transpose_dict : encrypted_message += transpose_dict [char] else: encrypted_message += char return encrypted_message

37. class EncryptedSubMessage ( SubMessage ): def __init__(self, text): ''' Initializes an EncryptedSubMessage object text (string): the message's text an EncryptedSubMessage object inherits from SubMessage and has two attributes: self.message_text (string, determined by input text) self.valid_words (list, determined using helper function load_words ) ''' super().__init__(text) def decrypt_message (self): ''' Attempt to decrypt the encrypted message Idea is to try each permutation of the vowels and test it on the encrypted message. Use the permutation that creates the maximum number of valid English words.

38. Returns: the best decrypted message ''' best_decryption = self.message_text max_valid_words = 0 for perm in get_permutations (' aeiou '): transpose_dict = self.build_transpose_dict (perm) decrypted_message = self.apply_transpose ( transpose_dict ) words = decrypted_message.split () valid_word_count = sum( is_word ( self.valid_words , word) for word in words) if valid_word_count > max_valid_words : max_valid_words = valid_word_count best_decryption = decrypted_message return best_decryption

39. # Test cases if __name__ == '__main__': # Test cases for SubMessage message = SubMessage ("Hello World!") permutation = " eaiuo " transpose_dict = message.build_transpose_dict (permutation) print( f"Original message: { message.get_message_text ()}\ nPermutation : {permutation}\ nExpected encrypted message: Hillo Werld !\ nActual encrypted message: { message.apply_transpose ( transpose_dict )}\n") message = SubMessage ("Goodbye!") permutation = " iouae " transpose_dict = message.build_transpose_dict (permutation) print( f"Original message: { message.get_message_text ()}\ nPermutation : {permutation}\ nExpected encrypted message: Guddbyi !\ nActual encrypted message: { message.apply_transpose ( transpose_dict )}\n") # Test cases for EncryptedSubMessage encrypted_message = EncryptedSubMessage (" Hillo Werld !") print( f"Encrypted message: Hillo Werld !\ nExpected decrypted

40. message: Hello World!\ nActual decrypted message: { encrypted_message.decrypt_message ()}\n") encrypted_message = EncryptedSubMessage (" Guddbyi !") print( f"Encrypted message: Guddbyi !\ nExpected decrypted message: Goodbye!\ nActual decrypted message: { encrypted_message.decrypt_message ()}\n") For information about citing these materials or our Terms of Use, visit: https://www.programmingassignmenthelper.com/