CS145 F2021 Project 7

proj7_starter.py

###
# Recursive GCD:
#
# One of the oldest known algorithms, dating back to the
# 5th century BCE, is Euclid’s algorithm for computing the
# greatest common divisor (GCD) of two integers.
#
# The GCD of 36 and 24 is 12.
# It works as follows:
# Let a, b be positive integers.
# Let rem be the remainder of a / b.
# If rem is 0, then GCD(a,b) is b.
# Otherwise, GCD(a,b) is the same as GCD(b,rem).


def gcd(a: int, b: int) -> int:
    # OK to assume that a is greater than b.
    # GCD may be written with a loop or recursion; but recursion is closer to the hints.
    return 0  # replace this


def test_gcd():
    assert gcd(7, 3) == 1
    assert gcd(36, 24) == 12


def minimum(xs):
    # This solution must be recursive
    return xs[0]


def test_minimum():
    assert minimum([]) == None
    assert minimum([4]) == 4
    assert minimum([4, 3]) == 3
    assert minimum([1, 2, 3, 4]) == 1
    assert minimum([4, 3, 2, 1]) == 1


def is_palindrome(data):
    # This solution must be recursive
    # Try slicing off the first and last elements as you recurse.
    return False


def test_is_palindrome():
    # empty should be True.
    assert is_palindrome("")
    assert is_palindrome([])
    # lists of length 1 should be True.
    assert is_palindrome("a")
    assert is_palindrome([1])

    # More difficult examples:
    assert not is_palindrome("xy")
    assert not is_palindrome([2, 3])
    assert is_palindrome("abcba")
    assert is_palindrome("abba")
    assert not is_palindrome("abxyba")
    assert is_palindrome([1, 2, 1])
    assert not is_palindrome([1, 2, 3, 4, 2, 1])

if __name__ == "__main__":
    import pytest

    pytest.main([__file__])