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

Map

We wrote the recursive version of the function map in lecture. Here it is again:

map takes

  • m - a one-argument function that you want to map onto each element in the list.
  • s - a sequence of values
def map(f, s):
    """
    Map a function f onto a sequence.

    >>> def double(x):
    ...     return x * 2
    >>> def square(x):
    ...     return x ** 2
    >>> def toLetter(x):
    ...     alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    ...     return alpha[x%26]
    >>> map(double, [1,2,3,4])
    [2, 4, 6, 8]
    >>> map(square, [1, 2, 3, 4, 5, 10])
    [1, 4, 9, 16, 25, 100]
    >>> map(toLetter, [3, 0, 19, 0])
    ['d', 'a', 't', 'a']

    """
    if s == []:
        return s
    return [f(s[0])] + map(f, s[1:])

Required Questions

Question 1: Filter

Write the recursive version of the function filter which takes

  • filter - a one-argument function that returns True if the argument passed in should be included in the list, and False otherwise.
  • s - a sequence of values
def filter(f, s):
    """Filter a sequence to only contain values allowed by filter.

    >>> def is_even(x):
    ...     return x % 2 == 0
    >>> def divisible_by5(x):
    ...     return x % 5 == 0
    >>> filter(is_even, [1,2,3,4])
    [2, 4]
    >>> filter(divisible_by5, [1, 4, 9, 16, 25, 100])
    [25, 100]
    """
    if s == []:
        return s
    if f(s[0]):
        return [s[0]] + filter(f, s[1:])
    return filter(f, s[1:])

Use OK to test your code:

python3 ok -q filter

Question 2: Reduce

Write the recursive version of the function reduce which takes

  • reducer - a two-argument function that reduces elements to a single value
  • s - a sequence of values
  • base - the starting value in the reduction. This is usually the identity of the reducer

If you're feeling stuck, think about the parameters of reduce.

from operator import add, mul

def reduce(reducer, s, base):
    """Reduce a sequence under a two-argument function starting from a base value.

    >>> def add(x, y):
    ...     return x + y
    >>> def mul(x, y):
    ...     return x*y
    >>> reduce(add, [1,2,3,4], 0)
    10
    >>> reduce(mul, [1,2,3,4], 0)
    0
    >>> reduce(mul, [1,2,3,4], 1)
    24
    """
    if s == []:
        return base
    next_base = reducer(base, s[0])
    return reduce(reducer, s[1:], next_base)

Use OK to test your code:

python3 ok -q reduce

Question 3: In summation...

Write the recursive version of summation, which takes two arguments, a number n and a function term, applies term to every number between 1 and n inclusive, and returns the sum of those results.

def summation(n, term):
    """Return the sum of the 0th to nth terms in the sequence defined
    by term.
    Should be implemented using recursion.

    >>> summation(5, lambda x: x * x * x)
    225
    >>> summation(9, lambda x: x + 1)
    55
    >>> summation(5, lambda x: 2**x)
    63
    """
    if n == 0:
        return term(0)
    return term(n) + summation(n - 1, term)

Use OK to test your code:

python3 ok -q summation

Question 4: Ten-Pairs

Write a function that takes a positive integer n and returns the number of times the number digit appears. Do not use any assignment statements.

def count_digit(n, digit):
    """Return how many times digit appears in n.

    >>> count_digit(55055, 5)
    4
    >>> count_digit(1231421, 1)
    3
    >>> count_digit(12, 3)
    0
    """
    if n == 0:
        return 0
    if n%10 == digit:
        return count_digit(n//10, digit) + 1
    else:
        return count_digit(n//10, digit)

Use OK to test your code:

python3 ok -q count_digit

Write a function that takes a positive integer n and returns the number of ten-pairs it contains. A ten-pair is a pairs of digits within n that sum to 10. Do not use any assignment statements.

The number 7,823,952 has 3 ten-pairs. The first and fourth digits sum to 7+3=10, the second and third digits sum to 8+2=10, and the second and last digit sum to 8+2=10:

Hint: What if you had a function that counted the times a certain digit appeared.

def ten_pairs(n):
    """Return the number of ten-pairs within positive integer n.

    >>> ten_pairs(7823952)
    3
    >>> ten_pairs(55055)
    6
    >>> ten_pairs(9641469)
    6
    """
    if n < 10:
        return 0
    else:
        return ten_pairs(n//10) + count_digit(n//10, 10 - n%10)

def count_digit(n, digit):
    """Return how many times digit appears in n.

    >>> count_digit(55055, 5)
    4
    """
    if n == 0:
        return 0
    else:
        if n%10 == digit:
            return count_digit(n//10, digit) + 1
        else:
            return count_digit(n//10, digit)

Use OK to test your code:

python3 ok -q ten_pairs

Challenge Questions - Optional

Question 5: 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 6: Binary

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

def binary(n):
    """Return a list representing the representation of a number in base 2.

    >>> binary(55055)
    [1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
    >>> binary(-136)
    ['-', 1, 0, 0, 0, 1, 0, 0, 0]
    """
    if n < 0:
        return ['-'] + binary(-1 * n)
    elif n < 2:
        return [n % 2]
    else:
        return binary(n // 2) + [n % 2]

Use OK to test your code:

python3 ok -q binary