# Lab 4: Recursion

*Due by 11:59pm on Friday, September 27.*

## Starter Files

Download lab04.zip.

# Required Questions

## Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

## Recursion

### Q1: Double Eights

Write a **recursive** function that takes in a positive integer `n`

and determines if its
digits contain two adjacent `8`

s (that is, two `8`

s right next to each other).u

Hint:Start by coming up with a recursive plan: the digits of a number have double eights if either (think of something that is straightforward to check) or double eights appear in the rest of the digits.

**Important:** Use recursion; the tests will fail if you use any loops (for, while).

```
def double_eights(n):
"""Returns whether or not n has two digits in row that
are the number 8.
>>> double_eights(1288)
True
>>> double_eights(880)
True
>>> double_eights(538835)
True
>>> double_eights(284682)
False
>>> double_eights(588138)
True
>>> double_eights(78)
False
>>> # ban iteration
>>> from construct_check import check
>>> check(LAB_SOURCE_FILE, 'double_eights', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q double_eights`

### Q2: Summation

Write a recursive implementation of `summation`

, which takes a positive
integer `n`

and a function `term`

. It applies `term`

to every number from `1`

to `n`

including `n`

and returns the sum.

**Important:** Use recursion; the tests will fail if you use any loops (for, while).

```
def summation(n, term):
"""Return the sum of numbers 1 through n (including n) wíth term applied to each number.
>>> summation(5, lambda x: x * x * x) # 1^3 + 2^3 + 3^3 + 4^3 + 5^3
225
>>> summation(9, lambda x: x + 1) # 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
54
>>> summation(5, lambda x: 2**x) # 2^1 + 2^2 + 2^3 + 2^4 + 2^5
62
>>> # ban iteration
>>> from construct_check import check
>>> check(LAB_SOURCE_FILE, 'summation', ['While', 'For'])
True
"""
assert n >= 1
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q summation`

### Q3: Ten-Pairs

Write a function that takes a positive integer `n`

and returns the
number of ten-pairs it contains. A ten-pair is a pair of digits
within `n`

that sums to 10.

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.

Important notes:

- A digit can be part of more than one ten-pair.
- One 5 does not make a ten-pair with itself.

Recommended: Complete and use the helper function`count_digit`

to calculate how many times a digit appears in`n`

.

**Important:** Use recursion; the tests will fail if you use any loops (for, while).

```
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
>>> # ban iteration
>>> from construct_check import check
>>> check(LAB_SOURCE_FILE, 'ten_pairs', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"
def count_digit(n, digit):
"""Return how many times digit appears in n.
>>> count_digit(55055, 5)
4
>>> from construct_check import check
>>> # ban iteration
>>> check(LAB_SOURCE_FILE, 'count_digits', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q ten_pairs`

## Check Your Score Locally

You can locally check your score on each question of this assignment by running

`python3 ok --score`

**This does NOT submit the assignment!** When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

# Submit Assignment

Submit this assignment by uploading any files you've edited **to the appropriate Gradescope assignment.** Lab 00 has detailed instructions.