Lab 7: More Recursion
Due at 11:59:59 pm on Tuesday, 10/19/2021.

Starter Files

Download lab07.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

• Submit the lab07.py file to ok.

Questions

Question 1: Sum Digit Differences

Write the recursive function sum_diffs which takes in n, a number, and returns the sum of the differences between adjacent digits in the number n.

def sum_diffs(n):
    """ Return the sum of the differences between adjacent digits in the number n.

    >>> sum_diffs(8)
    0
    >>> sum_diffs(154) # 4 + 1 = 5
    5
    >>> sum_diffs(12321) # 1 + 1 + 1 + 1
    4
    >>> sum_diffs(7351) # 4 + 2 + 4
    10
    """
    "*** YOUR CODE HERE ***"
    if n < 10:
        return 0
    else:
        dif = abs(n % 10 - (n // 10)% 10)
        return dif + sum_diffs(n // 10)

Use OK to test your code:

python3 ok -q sum_diffs

Question 2: 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 diferent paths (only 3 are shown above).

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 == 1 or n == 1:
        return 1
    return paths(m - 1, n) + paths(m, n - 1)

Use OK to test your code:

python3 ok -q paths

Question 3: G function

A mathematical function G on positive integers is defined by two cases:

G(n) = n,                                       if n <= 3
G(n) = G(n - 1) + 2 * G(n - 2) + 3 * G(n - 3),  if n > 3

Write a recursive function g that computes G(n).

def g(n):
    """Return the value of G(n), computed recursively.

    >>> g(1)
    1
    >>> g(2)
    2
    >>> g(3)
    3
    >>> g(4)
    10
    >>> g(5)
    22
    """
    "*** YOUR CODE HERE ***"
    if n in (1, 2, 3):
        return n
    return g(n-1) + 2*g(n-2) + 3*g(n-3)
# Iterative solution, if you're curious
def g_iter(n):
    """Return the value of G(n), computed iteratively.

    >>> g_iter(1)
    1
    >>> g_iter(2)
    2
    >>> g_iter(3)
    3
    >>> g_iter(4)
    10
    >>> g_iter(5)
    22
    """
    if n == 1 or n == 2 or n == 3:
        return n
    a, b, c = 1, 2, 3
    while n > 3:
        a, b, c = b, c, c + 2*b + 3*a
        n = n - 1
    return c

Use OK to test your code:

python3 ok -q g

Submit

Make sure to submit this assignment by running:

python3 ok --submit