Solutions: You can find the file with solutions for all questions here.

Question 1: Hailstone

For the hailstone function from previously, you pick a positive integer n as the start. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process until n is 1. Write a recursive version of hailstone that prints out the values of the sequence and returns the number of steps.

def hailstone_iterative(n):
    """Print out the hailstone sequence starting at n, and return the
    number of elements in the sequence.

    >>> a = hailstone_iterative(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    print(n)
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + hailstone_iterative(n // 2)
    else:
        return 1 + hailstone_iterative(3 * n + 1)

def hailstone_recursive(n):
    """Print out the hailstone sequence starting at n, and return the
    number of elements in the sequence.

    >>> a = hailstone_recursive(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    print(n)
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + hailstone_recursive(n // 2)
    else:
        return 1 + hailstone_recursive(3 * n + 1)

Use OK to test your code:

python3 ok -q hailstone_iterative
python3 ok -q hailstone_recursive

Question 2: is_palindrome

Write a recursive solution for the function is_palindrome such that it takes in any list and returns True if that list is the same way going forwards and backwards.

def is_palindrome(lst):
    """ Returns True if the list is a palindrome. A palindrome is a list 
    that reads the same forwards as backwards
    >>> is_palindrome([1, 2, 3, 4, 5])
    False
    >>> is_palindrome(["p", "a", "l", "i", "n", "d", "r", "o", "m", "e"])
    False
    >>> is_palindrome([True, False, True])
    True
    >>> is_palindrome([])
    True
    >>> is_palindrome(["a", "l", "a", "s", "k", "a"])
    False
    >>> is_palindrome(["r", "a", "d", "a", "r"])
    True
    >>> is_palindrome(["f", "o", "o", "l", "p", "r", "o", "o", "f"])
    False
    >>> is_palindrome(["a", "v", "a"])
    True
    >>> is_palindrome(["racecar", "racecar"])
    True
    >>> is_palindrome(["r", "a", "c", "e", "c", "a", "r"])
    True
    """
    if len(lst) == 0 or len(lst) == 1:
        return True
    if lst[0] != lst[-1]:
        return False
    return is_palindrome(lst[1:-1])

Use OK to test your code:

python3 ok -q is_palindrome

Review

Here is the link to the prior semester's midterm. You must submit your completed, scanned version to Gradescope to receive credit. This portion of the homework will be graded on completion, but it is in your best interest to use this exam as practice for your upcoming midterm.

Fall 2019 Midterm