Preparation

a. Create a folder called lab-10-29 in your StuWork directory.

b. Open a Terminal and navigate to your lab-10-29 directory.

c. Create a file named data_processing.py and put all of the code from it today in there.

Exercise 1

Consider the following implementation of the largest procedure that returns the largest element of a list.

def largest(numbers):
    if len(numbers) == 1:
        return numbers[0]
    else:
        first = numbers[0]
        the_rest = numbers[1:]
        return max(first, largest(the_rest))

a. Copy and paste the above code into your lab file, open up a REPL, and import the largest function into the REPL.

b. Test the largest function by executing it on a variety of inputs.

c. What do you think happens if you run largest on a singleton list? Verify this in the REPL.

d. What do you think happens if you run largest on the empty list? Verify this in the REPL.

e. What do you think happens if you run largest on lists with non-numeric elements? Verify this in the REPL.

f. Add the following line of code immediately before the return statement:

print("        ==> max({}, largest({}))".format(first, the_rest))

g. Close and reopen the REPL to refresh its definition of the largest function. Now execute largest on a variety of inputs to trace the recursion through to the base case.

Exercise 2

Consider the following function select_strings that extracts the strings out of a list.

def select_strings(lst):
    if len(lst) == 0:
        return []
    elif type(lst[0]) == str:
        # If the first element is a string, add it to the list of
        # the rest of the strings in the list
        return [lst[0]] + select_strings(lst[1:])
    else:
        # Otherwise return just the strings in the rest of the list
        return select_strings(lst[1:])

a. Copy and paste the above code into the lab file and import it into the REPL.

b. Discuss the code with your partner and make sure you understand each of the components.

c. Execute the code on a variety of inputs and ensure that it is extracting out the strings as expected.

Exercise 3

Consider the following function is_palindrome that checks if a string is the same if read both forwards and backwards. An example of a palindrome is “civic”.

def is_palindrome(s):
    if len(s) <= 1:
        return True
    else:
        # Checks if the first character is equal to the last
        # and checks if the substring excluding the first and
        # last characters is also a palindrome
        return (s[0] == s[-1]) and is_palindrome(s[1:-1])

a. Copy and paste the above code into the lab file and import it into the REPL.

b. Discuss the code with your partner and make sure you understand each of the components.

c. Execute the code on a variety of inputs and ensure that it is working as expected.

d. Add the following line of code immediately before the if statement (just after the declaration of the function):

print('is_palindrome("' + s + '")')

e. Execute is_palindrome on a variety of strings and watch how it recurses.

Exercise 4

Suppose that the len function was not written for lists. How might we implement it? We could remove one element from the list, make a recursive call, and then add one.

a. Using this idea, write a recursive function list_len that takes in a list as a parameter and returns the length of the list. You may not use len for this.

b. Check your answer on a variety of inputs. (Be sure to check the empty list, too)

Exercise 5

Suppose that we want to count the number of occurrences of a certain value val in a list lst. Using a similar idea from exercise 2, write a recursive function called count(lst, val) that returns the number of times val appears in lst.

Check your answer on a variety of inputs including the empty list.

Exercise 6

Now let’s try implementing a function similar to range. Recall that range(n) returns a sequence of numbers starting at 0 and ending at n-1. Recursion could be helpful in implementing this procedure.

Write a recursive function called list_range(n) that takes in a number n and returns a list that contains all the integers between 0 and n-1.

Exercise 7

Using a technique similar to exercise 3, write a recursive function called reverse(s) that takes in a string as a parameter and returns a new string that has the characters in the reverse order. Thus, reverse("abc") returns the string "cba".