Please make sure to follow all the requirements (bolded) and solve everything using recursion (NO INNER or LAMBDA FUNCTIONS )

USE PYTHON3; DO NOT IMPORT ANY PACKAGES

1.

a)

Write a recursive function that simulates the functionality of str.count(). The function takes a string (s) and a substring (substr), and counts how many times the substring appears (non-overlapping) in the string. This function is case-sensitive.

If the input substring is an empty string, the function returns one plus the number of characters in s. For example, count_substr("hello", "") returns 6, as you can imagine there are 6 "cursor positions" in "hello":

h e l l o

^ ^ ^ ^ ^ ^

Requirement:

You cannot use for, while, map() and filter(). You cannot use any built-in string functions to count the substring. You cannot use a recursive helper function, including an inner function.

def count_substr(s, substr):

"""

>>> count_substr('hello', '')

6

>>> count_substr('pen pineapple apple pen', 'apple')

2

>>> count_substr('oo ooo oooo ooooo oooooo', 'ooo')

5

"""

# YOUR CODE GOES HERE #

b)

Encoding is a process of converting a piece of information into a coded form with a predefined rule. To encode a string, the common practice is to have a mapping dictionary that records how each pattern (substring) is encoded.

Write a recursive encoding function that adapts a special mapping dictionary to encode a given piece of text (plaintext). The mapping dictionary will have characters (strings of length 1) as keys, and strings of length 3 as values. This function will lookup each character of the plaintext in the mapping dictionary, and replace this character with the corresponding 3-character pattern.

You can assume that all characters in the plaintext will always appear as keys in the mapping. Also, note that a dictionary can have duplicate values, meaning that multiple characters can be encoded to the same 3-character pattern.

Requirement: You cannot use for, while, map() and filter(). You cannot use any built-in functions to replace characters. You cannot use a recursive helper function, including an inner function.

def encode(mapping, plaintext): """ >>> mapping = {'z': 'not', 'r': 'ece', 't': 'dsc'} >>> encode(mapping, 'zzr') 'notnotece' >>> encode(mapping, 'zzt') 'notnotdsc' >>> encode(mapping, 'ttzrr') 'dscdscnoteceece' """ # YOUR CODE GOES HERE #

c)

Given a non-negative integer num, write a recursive function that repeatedly adds all digits together until the result becomes a single-digit number.

Requirement: You cannot use map() and filter(). However, you can use loops to sum up the digits. You cannot use a recursive helper function, including an inner function.

Examples: 41 (4 + 1) = 5 567 (5 + 6 + 7) = 18 (1 + 8) = 9 999777 (9 + 9 + 9 + 7 + 7 + 7) = 48 (4 + 8) = 12 (1 + 2) = 3

def add_all_digits(num): """ >>> add_all_digits(41) 5 >>> add_all_digits(567) 9 >>> add_all_digits(999777) 3 """ # YOUR CODE GOES HERE # d)

Write a recursive function that returns the smallest element in the input list. You can assume that the input list will have at least one element.

Requirement: You cannot use for, while, map() and filter(). You cannot use the built-in min(), min() or sorting functions. You cannot use a recursive helper function, including an inner function.

def find_min_recursive(lst): """ >>> find_min_recursive([1, 2, 3, 4, 5]) 1 >>> find_min_recursive([10, 11, 5, 0, -10, 1]) -10 >>> find_min_recursive(['b', 'c', 'z', 'y', 'a', 'e']) 'a' """ # YOUR CODE GOES HERE #