Lab 6: Recursion and Midterm Review

Due at 11:59:59 pm on 10/22/2019.

Starter Files

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

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

When you are ready to submit, run ok with the --submit option:

python3 ok --submit

After submitting, ok will display a submission URL, with which you can view your submission on okpy.org.

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: A Bad List Flattener

There is something wrong with the following code! Figure out what is wrong with it, and then fix it to pass the doc string.

Hint, your fix should be very minor! Do not rewrite the whole program.

def bad_list_flattener(lst1, lst2):
    """
    Flattens both lst1 and lst2, and returns the 
    concatenation of the two flattened lists. Flattening 
    a list means to collapse the list into one 
    dimension (like np.flatten).
    >>> girls = [['Rachel', 'Green'], ['Phoebe', 'Buffay']]
    >>> boys = [['Ross', 'Geller'], ['Chandler', 'Bing']]
    >>> bad_list_flattener(girls, boys)
    ['Rachel', 'Green', 'Phoebe', 'Buffay', 'Ross', 'Geller', 'Chandler', 'Bing']
    >>> cats = [['Persian'], ['British', 'Shorthair']]
    >>> dogs = [['Golden', 'Retriever']]
    >>> bad_list_flattener(dogs, cats)
    ['Golden', 'Retriever', 'Persian', 'British', 'Shorthair']
    """
    newlist1 = []
    newlist2 = []
    for inner_lst in lst1:
        for item in inner_lst:
            newlist1 += item
    for inner_lst in lst2:
        for item in inner_lst:
            newlist2 += item
    return newlist1 + newlist2
def bad_list_flattener(lst1, lst2):
    """
    Flattens both lst1 and lst2, and returns the 
    concatenation of the two flattened lists. Flattening 
    a list means to collapse the list into one 
    dimension (like np.flatten).
    >>> girls = [['Rachel', 'Green'], ['Phoebe', 'Buffay']]
    >>> boys = [['Ross', 'Geller'], ['Chandler', 'Bing']]
    >>> bad_list_flattener(girls, boys)
    ['Rachel', 'Green', 'Phoebe', 'Buffay', 'Ross', 'Geller', 'Chandler', 'Bing']
    >>> cats = [['Persian'], ['British', 'Shorthair']]
    >>> dogs = [['Golden', 'Retriever']]
    >>> bad_list_flattener(dogs, cats)
    ['Golden', 'Retriever', 'Persian', 'British', 'Shorthair']
    """
    newlist1 = []
    newlist2 = []
    for inner_lst in lst1:
        for item in inner_lst:
            newlist1 += item
    for inner_lst in lst2:
        for item in inner_lst:
            newlist2 += item
    return newlist1 + newlist2

Use OK to test your code:

python3 ok -q bad_list_flattener

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])

Use OK to test your code:

python3 ok -q is_palindrome

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 nonnegative 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)

Use OK to test your code:

python3 ok -q ab_plus_c

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)

Use OK to test your code:

python3 ok -q gcd

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
    """
    while a % b != 0:
        a, b = b, a % b
    return b

Question 5: Adding matrices

To practice, write a function that adds two matrices together using list comprehensions. The function should take in two 2D lists of the same dimensions. Try to implement this in one line!

def add_matrices(x, y):
    """
    >>> matrix1 = [[1, 3],
    ...            [2, 0]]
    >>> matrix2 = [[-3, 0],
    ...            [1, 2]]
    >>> add_matrices(matrix1, matrix2)
    [[-2, 3], [3, 2]]
    """

    "*** YOUR CODE HERE ***"
    

    return [[x[i][j] + y[i][j] for j in range(len(x[0]))]
                               for i in range(len(x))]

Use OK to test your code:

python3 ok -q add_matrices

Question 6: Mul_by_num

Using higher order functions, complete the mul_by_num function. This function should take an argument and return a one argument function that multiplies any value passed to it by the original number.

def mul_by_num(num):
    """
    Returns a function that takes one argument and returns num
    times that argument.
    >>> x = mul_by_num(5)
    >>> y = mul_by_num(2)
    >>> x(3)
    15
    >>> y(-4)
    -8
    """

    "*** YOUR CODE HERE ***"
    

    def f(x):
        return num*x
    return f

Use OK to test your code:

python3 ok -q mul_by_num

Question 7: Skip Add

Write a function skip_add that takes a single argument n and computes the sum of every other integer between 0 and n starting from n. Assume n is non-negative.

def skip_add(n):
    """ Takes a number x and returns x + x-2 + x-4 + x-6 + ... + 0.

    >>> skip_add(5)  # 5 + 3 + 1 + 0
    9
    >>> skip_add(10) # 10 + 8 + 6 + 4 + 2 + 0
    30
    """

    "*** YOUR CODE HERE ***"

    if n <= 0:
        return 0
    return n + skip_add(n - 2)

Use OK to test your code:

python3 ok -q skip_add

Extra Questions

Extra questions are not worth extra credit and are entirely optional. They are designed to challenge you to think creatively!

Question 8: Towers of Hanoi

A classic puzzle called the Towers of Hanoi is a game that consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with n disks in a neat stack in ascending order of size on a start rod, the smallest at the top, forming a conical shape.

Towers of Hanoi

The objective of the puzzle is to move the entire stack to an end rod, obeying the following rules:

  • Only one disk may be moved at a time.
  • Each move consists of taking the top (smallest) disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
  • No disk may be placed on top of a smaller disk.

Complete the definition of move_stack, which prints out the steps required to move n disks from the start rod to the end rod without violating the rules.

def print_move(origin, destination):
    """Print instructions to move a disk."""
    print("Move the top disk from rod", origin, "to rod", destination)

def move_stack(n, start, end):
    """Print the moves required to move n disks on the start pole to the end
    pole without violating the rules of Towers of Hanoi.

    n -- number of disks
    start -- a pole position, either 1, 2, or 3
    end -- a pole position, either 1, 2, or 3

    There are exactly three poles, and start and end must be different. Assume
    that the start pole has at least n disks of increasing size, and the end
    pole is either empty or has a top disk larger than the top n start disks.

    >>> move_stack(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> move_stack(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> move_stack(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"

    "*** YOUR CODE HERE ***"

    if n == 1:
        print_move(start, end)
    else:
        other = 6 - start - end
        move_stack(n-1, start, other)
        print_move(start, end)
        move_stack(n-1, other, end)

Use OK to test your code:

python3 ok -q move_stack