Solutions: You can find the file with solutions for all questions here.

Recursion

Question 1: Decimal

Write the recursive version of the function decimal which takes in n, a number, and returns a list representing the decimal representation of the number.

def decimal(n):
    """Return a list representing the decimal representation of a number.

    >>> decimal(55055)
    [5, 5, 0, 5, 5]
    >>> decimal(-136)
    ['-', 1, 3, 6]
    """
    if n < 0:
        return ['-'] + decimal(-1 * n)
    elif n < 10:
        return [n % 10]
    else:
        return decimal(n // 10) + [n % 10]

Use OK to test your code:

python3 ok -q decimal

Question 2: Hailstone

For the hailstone function from previously, you pick a positive integer n as the start. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process until n is 1. Write a recursive version of hailstone that prints out the values of the sequence and returns the number of steps.

def hailstone_iterative(n):
    """Print out the hailstone sequence starting at n, and return the
    number of elements in the sequence.

    >>> a = hailstone_iterative(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    print(n)
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + hailstone_iterative(n // 2)
    else:
        return 1 + hailstone_iterative(3 * n + 1)

def hailstone_recursive(n):
    """Print out the hailstone sequence starting at n, and return the
    number of elements in the sequence.

    >>> a = hailstone_recursive(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    print(n)
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + hailstone_recursive(n // 2)
    else:
        return 1 + hailstone_recursive(3 * n + 1)

Use OK to test your code:

python3 ok -q hailstone_iterative
python3 ok -q hailstone_recursive

Question 3: 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", "l", "a", "s", "k", "a"])
    False
    >>> is_palindrome(["r", "a", "d", "a", "r"])
    True
    >>> is_palindrome(["f", "o", "o", "l", "p", "r", "o", "o", "f"])
    False
    >>> is_palindrome(["a", "v", "a"])
    True
    >>> is_palindrome(["racecar", "racecar"])
    True
    >>> is_palindrome(["r", "a", "c", "e", "c", "a", "r"])
    True
    """
    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

Submit

Make sure to submit this assignment by running:

python3 ok --submit