# Lab 8: Recursion

# rlist functions for question 0
empty_rlist = None

def make_rlist(first, rest):
    """Make a recursive list from its first element and the rest."""
    return (first, rest)
                
def first(s):
    """Return the first element of a recursive list s."""
    return s[0]
                                
def rest(s):
    """Return the rest of the elements of a recursive list s."""
    return s[1]

# Question 0 - Iterative Version
def contains_iterative(n, l):
    """Returns True if n is in rlist l and False otherwise.

    >>> foo_lst = make_rlist(1, make_rlist(2, make_rlist(3, empty_rlist)))
    >>> contains_iterative(5, foo_lst)
    False
    >>> contains_iterative(1, foo_lst)
    True
    """
    "*** YOUR CODE HERE ***"


# Question 0 - Recursive Version
def contains_recursive(n, l):
    """Returns True if n is in rlist l and False otherwise.

    >>> foo_lst = (1, (2, (3, (4, None))))
    >>> contains_recursive(5, foo_lst)
    False
    >>> contains_recursive(1, foo_lst)
    True
    """
    "*** YOUR CODE HERE ***"


# Question 1 - Iterative Version
def gcd_iterative(a, b):
    """Find the greatest common divisor of a and b using the Euclidean
    algorithm.

    >>> gcd_iterative(2004, 100)
    4
    >>> gcd_iterative(100, 2004)
    4
    >>> gcd_iterative(2003, 2011)
    1
    >>> gcd_iterative(2000, 100)
    100
    """
    "*** YOUR CODE HERE ***"


# Question 1 - Recursive Version
def gcd_recursive(a, b):
    """Find the greatest common divisor of a and b using the Euclidean
    algorithm.

    >>> gcd_recursive(2004, 100)
    4
    >>> gcd_recursive(100, 2004)
    4
    >>> gcd_recursive(2003, 2011)
    1
    >>> gcd_recursive(2000, 100)
    100
    """
    "*** YOUR CODE HERE ***"


# Question 2
def binary_search(p, lst):
    """Return True if p is in the list lst using a recursive binary search.

    >>> test_lst1 = [1, 2, 4, 5, 16, 23, 38, 99, 105]
    >>> test_lst2 = [1, 2, 3, 22, 34, 88]
    >>> binary_search(5, test_lst1)
    True
    >>> binary_search(88, test_lst2)
    True
    >>> binary_search(3, test_lst1)
    False
    >>> binary_search(14, test_lst2)
    False
    """
    "*** YOUR CODE HERE ***"


# Question 3
def deep_map(fn, lst):
    """Like map, but also maps over all elements of any items which are lists.

    >>> deep_map(lambda x: x * x, [1, 2, [3, [4], 5], 6])
    [1, 4, [9, [16], 25], 36]
    >>> deep_map(lambda x: x + 2, [4, 22, [23, 35], 9])
    [6, 24, [25, 37], 11]
    """
    "*** YOUR CODE HERE ***"


# Question 4
def count_paths(length, width):
    """Count the number of ways to get from (0, 0) to (length - 1, width - 1)
    moving only down or right.

    >>> count_paths(2, 2)
    2
    >>> count_paths(3, 3)
    6
    """
    "*** YOUR CODE HERE ***"