Due at 9:00pm on 10/04/2018.

Starter Files

Download lab05.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

When you are done, submit the lab by uploading the lab05.py file to okpy.org. You may submit more than once before the deadline; only the final submission will be graded.

Recursion

A recursive function is a function that calls itself in its body, either directly or indirectly. Recursive functions have three important components:

1. Base case(s), the simplest possible form of the problem you're trying to solve.
2. Consider a recursive call on a smaller argument.
3. Recursive case(s), where the function calls itself with a simpler argument as part of the computation.

Let's look at the canonical example, factorial:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

We know by its definition that 0! is 1. So we choose n = 0 as our base case. The recursive step also follows from the definition of factorial, i.e. n! = n * (n-1)!.

The next few questions in lab will have you writing recursive functions. Here are some general tips:

• Consider how you can solve the current problem using the solution to a simpler version of the problem. Remember to trust the recursion: assume that your solution to the simpler problem works correctly without worrying about how.
• Think about what the answer would be in the simplest possible case(s). These will be your base cases - the stopping points for your recursive calls. Make sure to consider the possibility that you're missing base cases (this is a common way recursive solutions fail).
• It may help to write the iterative version first.

Required Questions

Question 1: Sine

Now we're going to approximate the sine trigonemetric function using 2 useful facts. One is that sin(x) is approximately equal to x as x gets small (for this question, below 0.0001). The other fact is the trigonometric identity

Using these two facts, write a function sine that returns the sine of a value in radians.

def sine(x):
    """Returns the value of sine(x), where x is a value in radians. Use 0.0001 as a threshold.

    >>> from math import pi
    >>> sine(pi) #Notice how the value is very small but not quite 0.
    -1.482085565385205e-09 
    >>> sine(pi/2)
    1.0
    >>> sine((7 * pi)/2)
    -1.0
    >>> sine(1.5)
    0.9974949867067586
    """
    "*** YOUR CODE HERE ***"
    if abs(x) < 0.0001:
        return x
    return 3 * sine(x / 3) - 4 * pow(sine(x / 3), 3)

Toggle Solution

Use OK to test your code:

python3 ok -q sine --local

Lists Review

In Data 8, you have recently started working with Tables. Tables are an extremely useful and powerful data type. In CS88 we will work with other data types. Python provides several important built-in data types that we can build from. So far, you have met numberical data types (ints, floats, and booleans) and one sequence type (strings). Lists, tuples, and dictionaries are other sequence data types in Python. Here, we will take a closer look at lists. A list can contain a sequence of values of any type.

You can create a list just by placing the values, separated by commas, within square brackets. Here are some examples. As you will see in one of the examples, lists can contain other lists.

>>> [1,2,3]
[1, 2, 3]
>>> ["frog", 3, 3.1415]
['frog', 3, 3.1415]
>>> [True, [1, 2], 42]
[True, [1, 2], 42]

Open up your python interpreter and create some lists of your own.
You learned last week that what really makes a data type useful is the operations that you can perform on it. What can you do with lists?

>>> x = [1,2,3]    # assign them to variables
>>> len(x)         # get their length, i.e., the number of elements in them
3
>>> x + [4,5]      # + is concatenation
[1, 2, 3, 4, 5]
>>> [1,2] * 3        # * is replication
[1, 2, 1, 2, 1, 2]
>>> len([1,2] * 3)
6
>>> [1,2] * [3,4]    # what's this?
TypeError: can't multiply sequence by non-int of type 'list'

The in operator is very useful when working with lists. It operates on the entire list and produces a boolean that answers the question, "Is this item in the list?".

>>> 2 in [1,2,3]
True
>>> "frog" in [1,2,3]
False
>>> [1,2] in [1,2,3]
False
>>> [1,2] in [[1,2],3]
True

Other cool things we can do with list is index them, and get slices of them

>>> lst = [2, 4, 6, 8, 10]
>>> lst[0]
2
>>> lst[1]
4
>>> lst[4]
10
>>> lst[-1] # this is how we get the last element!
10
>>> lst[1:]
[4, 6, 8, 10]
>>> lst[1:4] # list slicing, include the start, exclude the end
[4, 6, 8]
>>> lst[1:-1]
[4, 6, 8]
>>> lst[:3]
[2, 4, 6]
>>> lst[0:3]
[2, 4, 6]

Play around with this in your terminal!

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", "v", "a"])
    True
    >>> is_palindrome(["racecar", "racecar"])
    True
    >>> is_palindrome(["r", "a", "c", "e", "c", "a", "r"])
    True
    """
    "*** YOUR CODE HERE ***"
    if len(lst) == 0 or len(lst) == 1:
        return True
    if lst[0] != lst[-1]:
        return False
    return is_palindrome(lst[1:-1])

Toggle Solution

Use OK to test your code:

python3 ok -q is_palindrome --local

Question 3: AB Plus C

Implement ab_plus_c, a function that takes arguments a, b, and c and computes a * b + c. You can assume a and b are both positive integers. However, you can't use the * operator. Try recursion!

def ab_plus_c(a, b, c):
    """Computes a * b + c.

    >>> ab_plus_c(2, 4, 3)  # 2 * 4 + 3
    11
    >>> ab_plus_c(0, 3, 2)  # 0 * 3 + 2
    2
    >>> ab_plus_c(3, 0, 2)  # 3 * 0 + 2
    2
    """
    "*** YOUR CODE HERE ***"
    if b == 0:
        return c
    return a + ab_plus_c(a, b - 1, c)

Toggle Solution

Use OK to test your code:

python3 ok -q ab_plus_c --local

Question 4: GCD

The greatest common divisor of two positive integers a and b is the largest integer which evenly divides both numbers (with no remainder). Euclid, a Greek mathematician in 300 B.C., realized that the greatest common divisor of a and b is one of the following:

• the smaller value if it evenly divides the larger value, OR
• the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value

In other words, if a is greater than b and a is not divisible by b, then

gcd(a, b) == gcd(b, a % b)

Write the gcd function recursively using Euclid's algorithm.

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    "*** YOUR CODE HERE ***"
    a, b = max(a, b), min(a, b)
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

Toggle Solution

Use OK to test your code:

python3 ok -q gcd --local

This is an example of the elegance that recursive solutions permit. Here for comparison is an iterative solution.

# Iterative solution, if you're curious
def gcd_iter(a, b):
    """Returns the greatest common divisor of a and b, using iteration.

    >>> gcd_iter(34, 19)
    1
    >>> gcd_iter(39, 91)
    13
    >>> gcd_iter(20, 30)
    10
    >>> gcd_iter(40, 40)
    40
    """
    if a < b:
        a, b = b, a
    while a > b and not a % b == 0:
        a, b = b, a % b
    return b

Question 5: Remove from sequence

Complete the recursive function remove which removes the first element in a sequence that is equal to a specified value.

def first(s):
    """Return the first element in a sequence."""
    return s[0]

def rest(s):
    """Return all elements in a sequence after the first"""
    return s[1:]

def remove(x, s):
    """Remove first element equal to x from sequence s.

    >>> remove(1,[])
    []
    >>> remove(1,[1])
    []
    >>> remove(1,[1,1])
    [1]
    >>> remove(1,[2,1])
    [2]
    >>> remove(1,[3,1,2])
    [3, 2]
    >>> remove(1,[3,1,2,1])
    [3, 2, 1]
    >>> remove(5, [3, 5, 2, 5, 11])
    [3, 2, 5, 11]
    """
    "*** YOUR CODE HERE ***"
    if not s:
        return []
    elif first(s) == x:
        return rest(s)
    else:
        return [first(s)] + remove(x, rest(s))

Toggle Solution

Illustrated here is a more complete doctest that shows good testing methodology. It is a little cumbersome as documentation, but you'll want to think about it for your projects. Test every condition that might come up. Then you won't be surprised when it does.

Use OK to test your code:

python3 ok -q remove --local

Question 6: Recursive Min Sort

In Data8 you will find sort to be instrumental to analysis of data. In CS88 you get to build it. There are many sorting algorithms; they have interesting differences and elegant implementations. In lecture we saw a tree recursive formulation of Quick Sort based on the following thinking:

• Base: an empty list is sorted
• Recursive leap: to sort a list of length n, assume quick sort works for all lists of length < n; remove the first element, use it to split the rest into two sets (all less-or-equal and all greater), sort both recursively, and put the three pieces back together.

Review the lecture slides if this is unfamiliar to you. In this question we will build another sort algorithm and compare the two using some of your Data8 skills. Here is another idea for sorting.

• Base: an empty list is sorted
• Recursive leap: to sort a list of length n > 0, assume that your function will correctly sort lists of length n-1, remove the minimum element in the sequence; sort the remaining list of length n - 1 recursively, put the min element in front of the the sorted remainder.

You have been given a function to find the minimum element (recursively) and you just wrote function to remove the first occurence of an element (recursively).
Now you can use those to sort a list (recursively). Complete rsort

# Recursive Min Sort

# Helper function
def rmin(s):
    """Return the minimum value in a sequence."""
    if len(s) == 1:
        return first(s)
    else:
        return min(first(s), rmin(rest(s)))

def rsort(s):
    """Sort sequence s in ascending order.

    >>> rsort([])
    []
    >>> rsort([1])
    [1]
    >>> rsort([1, 1, 1])
    [1, 1, 1]
    >>> rsort([1, 2, 3])
    [1, 2, 3]
    >>> rsort([3, 2, 1])
    [1, 2, 3]
    >>> rsort([1, 2, 1])
    [1, 1, 2]
    >>> rsort([1,2,3, 2, 1])
    [1, 1, 2, 2, 3]
    """
    "*** YOUR CODE HERE ***"
    if not s:
        return []
    else:
        min_value = rmin(s)
        after_min = remove(min_value, s)
        return [min_value] + rsort(after_min)

Toggle Solution

Use OK to test your code:

python3 ok -q rsort --local