# 15-110 Summer 2017

## Lab 6

### Goals

The purpose of this lab is to teach you how to write recursive functions. When you are done, you should be able to
• 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

### Deliverables

1. multiply.py
2. blast_off.py
3. sum_odds.py
4. count_a_words.py
5. 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.

## Part 1 - Recursion with Integers

### 1.1 Class Activity

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.

$a \times b = \begin{cases} a & \text{if } b = 1 \\ a + {a} \times (b - 1) & \text{if } b > 1 \end{cases}$
  >>> 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()

• TA Demo: Draw the recursion tree of multiply().

### 1.2 Student Activity

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.

## Part 2 - Recursion with Lists

### 2.1 Class Activity

• 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()


### 2.2 Class Activity

• 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()


### 2.3 Student Activity

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()


### Challenge Problem:

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 lst does not contain any strings that start with "a". You many NOT assume that all the elements in the list are strings. You may not use loops in your function.

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()