#
Lab 7: More Recursion

*Due at 11:59:59 pm on Tuesday, 3/30/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: 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, 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]
"""
"*** 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 2: 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 3: 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`

## Required Practice Problems Open in a new window

These questions are a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.

You should answer the questions on the study tool, and once you are completed with the required problems on the tool for that week, you will receive an okpy secret key that you will need to submit to show completion of the practice problems on the tool. Copy paste that secret key into the `lab07_practice_problems`

function at the bottom, along with your okpy email in the first line. Then, to test that you've correctly completed the problem, you can run the following command.

Use OK to test your code:

`python3 ok -q practice_problems`

These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`