Solution Files

Required Questions

Recursion!

Q1: Symmetric List

A list is symmetric if it is the same from left to right as from right to left. For example, [1, 2, 3, 4, 3, 2, 1] is symmetric. Implement symmetric, a function that takes list l and check if l is a symmetric list, Use recursion!

def symmetric(l):
    """Returns whether a list is symmetric.
    >>> symmetric([])
    True
    >>> symmetric([1])
    True
    >>> symmetric([1, 4, 5, 1])
    False
    >>> symmetric([1, 4, 4, 1])
    True
    >>> symmetric(['l', 'o', 'l'])
    True
    """
    if len(l) <= 1:
        return True
    elif l[0] == l[-1]:
        return symmetric(l[1: -1])
    else:
        return False

Use Ok to test your code:

python3 ok -q symmetric
Copy
✂️

Q2: 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
    """
    a, b = max(a, b), min(a, b)
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

# 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:
        return gcd_iter(b, a)
    while a > b and not a % b == 0:
        a, b = b, a % b
    return b

Use Ok to test your code:

python3 ok -q gcd
Copy
✂️

Q3: AB+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 non-negative integers. However, you can't use the * operator. Use 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
    """
    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
Copy
✂️

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.