Lab 6 Solutions

Recursion

Question 1: AB Plus 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 nonnegative integers. However, you can't use the * operator. Try 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
    """
    "*** YOUR CODE HERE ***"
    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

Question 2: Filter

Write the recursive version of the function filter which returns a list and takes in

• f - a one-argument function that returns True if the passed in argument should be included in the resulting list or False otherwise
• seq - a list of values

Note that this is different from the built in filter function we learned previously, which returns a filter object, not a list.

def filter(f, seq):
    """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]
    >>> filter(is_even, [1])
    []
    >>> filter(is_even, [2])
    [2]
    >>> filter(is_even, [])
    []
    """
    "*** YOUR CODE HERE ***"
    
    if seq == []:
        return seq
    if f(seq[0]):
        return [seq[0]] + filter(f, seq[1:])
    return filter(f, seq[1:])

Use OK to test your code:

python3 ok -q filter

Question 3: Decimal

Write the recursive version of the function decimal which takes in an integer n and returns a list of its digits, the decimal representation of n. See the doctests to handle the case where n < 0.

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

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

Use OK to test your code:

python3 ok -q decimal

Question 4: Insect Combinatorics

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. (There is a closed-form solution to this problem, but try to answer it procedurally using recursion.)

For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 different paths (only 3 are shown above). Note that this problem uses tree recursion.

def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    "*** YOUR CODE HERE ***"
    if m == 0 or n == 0:
        return 0
    if m == 1 and n == 1:
        return 1
    return paths(m - 1, n) + paths(m, n - 1)

Use OK to test your code:

python3 ok -q paths