Preparation

a. Create a folder called lab-02-18 in your StuWork directory.

b. Open a Terminal and navigate to your lab-02-18 directory.

c. Create a file called recursion.py.

Exercise 1

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

def select_strings(lst):
    """Returns a list of all the strings in lst"""

    # If lst contains zero elements...
    if len(lst) == 0:
        # Then there are no strings to select, so return empty list
        return []

    # If the type of the first element is a string...
    elif type(lst[0]) == str:
        # Return it, along with any other strings we find in the
        # rest of the list
        return [lst[0]] + select_strings(lst[1:])

    # If the type of the first element is NOT a string...
    else:
        # Then 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 2

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 3

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 1, 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 4

Using a technique similar to exercise 2, 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".