- Identify the base case and recursive case of a given function
- Trace the execution of a given recursive function
- Draw a recursion tree for a given recursive function
- Implement simple recursive functions over different data types and multi-dimensional lists

`multiply.py``blast_off.py``sum_odds.py``count_a_words.py``list_a_words.py (Challenge)`

Place these files in a `lab6` folder. Before leaving lab,
zip up the `lab6` folder
and hand in the zip file.

In ` multiply.py ` write a recursive Python function ` multiply(a,b) ` that returns the product of ` a ` and ` b ` based on the following formula. Your function may not use loops. You may assume that both inputs are non-negative and that ` b ` >= 0.

>>> multiply(5,1) 5 >>> multiply(5,10) 50

To properly test your code, copy and paste the following test function ` test_multiply() ` and the call to ` test_multiply() ` into your ` multiply.py ` file before loading it.

def test_multiply(): print("Testing multiply()...", end="") assert(multiply(0, 3) == 0) assert(multiply(0, 0) == 0) assert(multiply(1, 2) == 2) assert(multiply(4, 6) == 24) assert(multiply(11, 11) == 121) print("Passed!") test_multiply()

In a new file ` blast_off.py `, write a recursive function ` blast_off(n) ` that will count down from ` n ` to ` 0 ` exclusive on sepearate lines then print out ` "Blast off!"`. Do not use loops in your code. You may assume that the input ` n ` is a positive number. Your function should return ` None`.

>>> blast_off(5) 5 4 3 2 1 Blast off!

You may test this function visually.

- Returning the tail, head, or part of a list:
`lst[1:]`,`lst[:len(list)-1]`,`lst[2:5]` - Accessing substrings of a string:
`s[0]`,`s[2:5]`In

`sum_odds.py`, write a recursive function`sum_odds(x)`that sums all the odd integers in the list`x`. You may assume that all elements are non-negative integers. The function should return`0`if the list is empty or does not contain any odd integers.>>> lst = [0, 3, 5, 1, 2, 3] >>> sum_odds(lst) 12

To test your code, copy and paste the following test function

`test_sum_odds()`and its call to your file`sum_odds.py`before you load it.def test_sum_odds(): print("Testing sum_odds()...", end="") x0 = [] assert(sum_odds(x0) == 0) x1 = [5] assert(sum_odds(x1) == 5) x2 = [1, 2, 3] assert(sum_odds(x2) == 4) x3 = [2, 4, 6, 8] assert(sum_odds(x3) == 0) x4 = [1, 2, 3, 4, 5, 6] assert(sum_odds(x4) == 9) print("Passed!") test_sum_odds()

- Accessing elements of multi-dimensional lists:
`lst[0][0]` - Checking the data type of a value:
`type()`

In ` sum_odds2.py`, modify the previous function so that it now takes in multi-dimensional lists. ` sum_odds2(x) ` should be a recursive function that sums all the odd integers in the multi-dimensional list ` x`. You may assume that all elements are non-negative integers. The function should return ` 0 ` if the list is empty or does not contain any odd integers.

>>> lst = [0, [[3, 5], 1], 2, 3] >>> sum_odds2(lst) 12

To test your code, copy and paste the following test function ` test_sum_odds2() ` and its call to your file ` sum_odds2.py ` before you load it.

def test_sum_odds2(): print("Testing sum_odds2()...", end="") x0 = [[1, 2], 3] assert(sum_odds2(x0) == 4) x1 = [1, [2, 3]] assert(sum_odds2(x1) == 4) x2 = [] assert(sum_odds2(x2) == 0) x3 = [2, [3], 1, [4]] assert(sum_odds2(x3) == 4) x4 = [2, [4, 6], 8] assert(sum_odds2(x4) == 0) x5 = [1, [2, [3, 4], 5], 6] assert(sum_odds2(x5) == 9) x6 = [[[], []], [[[]]]] assert(sum_odds2(x6) == 0) print("Passed!") test_sum_odds2()

In a file ` count_a_words.py`, write a recursive function ` count_a_words(lst) ` that takes as input a single dimensional list ` lst ` and returns the number of strings in the list that start with ` "a"`. Your function should return ` 0 ` if the list does not contain any strings that start with ` "a"`. You may NOT assume that all the elements in the list are strings. You may not use loops in your function. Note: ` "a" ` is not the same as ` "A"`.

>>> lst = ["hello", True, 1, "alligator", [], "apple"] >>> count_a_words(lst) 2

To test your code, copy and paste the following test function ` test_count_a_words() ` and its call to your file ` count_a_words.py ` before you load it.

def test_count_a_words(): print("Testing count_a_words()...", end="") lst0 = [1, "apple", "foo", "anaconda", True, []] assert(count_a_words(lst0) == 2) lst1 = ["alligator"] assert(count_a_words(lst1) == 1) lst2 = [True] assert(count_a_words(lst2) == 0) lst3 = ["alligator", "anaconda"] assert(count_a_words(lst3) == 2) lst4 = ["foo", "bar", "hello", "world"] assert(count_a_words(lst4) == 0) lst5 = [] assert(count_a_words(lst5) == 0) lst6 = ["Alligator", "alligator"] assert(count_a_words(lst6) == 1) print("Passed!") test_count_a_words()

In the same file ` count_a_words.py`, write a recursive function ` list_a_words(lst) ` that takes as input a single dimensional list ` lst ` and returns ** a new list of all the words in lst that begin with "a"**. Your function should return an empty list if

** Hint: This function is a fairly simple variation of count_a_words(). Remember, the only difference is the data type you want to return.**

>>> lst = [1, "apple", "foo", "anaconda", True, []] >>> list_a_words(lst) ['apple', 'anaconda']

To test your code, copy and paste the following test function ` test_list_a_words() ` and its call to your file ` count_a_words.py ` before you load it.

def test_list_a_words(): print("Testing list_a_words()...", end="") lst0 = [1, "apple", "foo", "anaconda", True, []] assert(list_a_words(lst0) == ["apple", "anaconda"]) lst1 = ["alligator"] assert(list_a_words(lst1) == ["alligator"]) lst2 = [True] assert(list_a_words(lst2) == []) lst3 = ["alligator", "anaconda"] assert(list_a_words(lst3) == ["alligator", "anaconda"]) lst4 = ["foo", "bar", "hello", "world"] assert(list_a_words(lst4) == []) lst5 = [] assert(list_a_words(lst5) == []) lst6 = ["Alligator", "alligator"] assert(list_a_words(lst6) == ["alligator"]) print("Passed!") test_list_a_words()