CS21 Lab 9: Recursion

  • Due Sunday, November 22, before midnight

Goals

  • Use recursion to solve problems

Requirements

  • Write recursive solutions for each of the functions below. You should not have any for loops or while loops in your solutions.

  • Your main function must test each of your functions on multiple test cases. You should test on each of the examples provided and you should write at least two more on your own. You can test your functions either by printing out the function you are calling (and verifying the answers are correct by visual inspection) or by using assert (and having python check your answers for you):

# using print and then visually inspecting the output
lst = [2, 8]
result = contains_even(lst)
print("contains_even(%s) = %s" % (lst, result))

# using assert and having python check your answers
assert contains_even(lst) == True

1. Contains an even number

Write a function called contains_even that takes a list of integers as its only parameter and returns True if the list contains an even number. Otherwise, this function returns False.

Put this function, along with the tests in main, in the file called recursion.py.

contains_even([1, 2, 3, 5, 8]) == True
contains_even([2, 8]) == True
contains_even([1, 3, 5]) == False

2. Summing the even numbers in a list

Write a function called sum_even that takes a list of integers as its only parameter and returns the sum of all of the even numbers in the list. For example

Add this function, along with the tests in main, to the recursion.py file that you started in the previous question.

sum_even([1, 2, 3, 5, 8]) == 10
sum_even([2, 8]) == 10
sum_even([1, 3, 5]) == 0

3. Summing every other element in a list

Write a function called sum_every_other that takes a list of integers as its only parameter and returns the sum of the 1st, 3rd, 5th, etc elements in the list.

Add this function, along with the tests in main, to the recursion.py file that you have been using.

sum_every_other([1, 2, 3, 5, 8]) == 1 + 3 + 8 == 12
sum_every_other([2, 8]) == 2
sum_every_other([1, 3, 5]) == 1 + 5 == 6

4. Evens only

Write a function called keep_evens that takes a list of integers as its only parameter and returns a new list with all of the odd numbers removed.

Add this function, along with the tests in main, to the recursion.py file that you have been using.

keep_evens([1, 2, 3, 5, 8]) == [2, 8]
keep_evens([2, 8]) == [2, 8]
keep_evens([1, 3, 5]) == []

5. No vowels

Write a function called no_vowels that takes a string as its only parameter and returns a new string with all of the vowels removed. (The letter y is not a vowel for this purpose.)

Add this function, along with the tests in main, to the recursion.py file that you have been using.

no_vowels("hello") == "hll"
no_vowels("sky") == "sky"
no_vowels("eieio") == ""

6. Xerox

Write a function called xerox(word, n) that takes a string, word, and a non-negative integer, n, as parameters and returns a string where the word appears n times. Note: Do not use string multiplication to solve this.

Add this function, along with the tests in main, to the recursion.py file that you have been using.

xerox("oink", 2) == "oinkoink"
xerox("go", 3) == "gogogo"
xerox("", 50) == ""

7. Binary search

Below is an implementation of binary search that uses recursion. Notice that in this implementation, we pass the values of low and high into the binary_search function. Read through the code below and then answer the questions underneath the code.


def binary_search(item, lst, low, high):
    """
    Purpose: Perform binary search on a list
    Parameters:
      - item, an item to search for in the list
      - lst, a list of items of the same type as the item
      - low, the lowest index in the list where the item could be
      - high, the highest index in the list where the item could be
    Return: the index of the item in the list or -1 if the list
      does not contain the item
    """
    if low > high:
        return -1

    mid = (low + high) // 2
    if lst[mid] == item:
        return mid
    elif lst[mid] < item:
        return binary_search(item, lst, mid+1, high)
    else:
        return binary_search(item, lst, low, mid-1)

def main():
    lst = [1, 3, 6, 8, 9, 12, 14]
    item = 9
    result = binary_search(item, lst, 0, len(lst)-1)
    if result == -1:
        print(item, "not found")
    else:
        print(item, "found at position", result)

main()

These questions should be answered in the Questions-09.txt file.

  1. What is the return type of the binary_search function?

  2. What is/are the base cases in the binary_search function?

  3. What is/are the recursive cases in the binary_search function?

  4. How many times would the function binary_search be called if you ran the code?

  5. Draw the stack diagram, stopping just before you would begin removing functions from the stack. Take a picture of your solution and upload it to gradescope.

8. Answer the Questionnaire

Please edit the Questions-09.txt file in your cs21/labs/09 directory and answer the questions in that file.

Once you’re done with that, run handin21 again.

Turning in your labs…​.

Remember to run handin21 to turn in your lab files! You may run handin21 as many times as you want. Each time it will turn in any new work. We recommend running handin21 after you complete each program or after you complete significant work on any one program.