## 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
"""
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
"""
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
"""
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``