# Homework 3: Recursion, Tree Recursion

*Due by 11:59pm on Friday, February 17*

## Instructions

Download hw03.zip. Inside the archive, you will find a file called
hw03.py, along with a copy of the `ok`

autograder.

**Submission:** When you are done, submit the assignment by uploading all code files you've edited to Gradescope. You may submit more than once before the deadline; only the
final submission will be scored. Check that you have successfully submitted
your code on Gradescope. See Lab 0 for more instructions on
submitting assignments.

**Using Ok:** If you have any questions about using Ok, please
refer to this guide.

**Readings:** You might find the following references
useful:

**Grading:** Homework is graded based on
correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus.
**This homework is out of 2 points.**

# 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.

### Q1: Num Eights

Write a recursive function `num_eights`

that takes a positive integer `n`

and
returns the number of times the digit 8 appears in `n`

.

**Important:**
Use recursion; the tests will fail if you use any assignment statements or loops.
(You can however use function definitions if you so wish.)

```
def num_eights(n):
"""Returns the number of times 8 appears as a digit of n.
>>> num_eights(3)
0
>>> num_eights(8)
1
>>> num_eights(88888888)
8
>>> num_eights(2638)
1
>>> num_eights(86380)
2
>>> num_eights(12345)
0
>>> num_eights(8782089)
3
>>> from construct_check import check
>>> # ban all assignment statements
>>> check(HW_SOURCE_FILE, 'num_eights',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q num_eights`

### Q2: Ping-pong

The ping-pong sequence counts up starting from 1 and is always either counting
up or counting down. At element `k`

, the direction switches if `k`

is a
multiple of 8 or contains the digit 8. The first 30 elements of the ping-pong
sequence are listed below, with direction swaps marked using brackets at the
8th, 16th, 18th, 24th, and 28th elements:

Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | [8] | 9 | 10 | 11 | 12 | 13 | 14 | 15 | [16] | 17 | [18] | 19 | 20 | 21 | 22 | 23 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

PingPong Value | 1 | 2 | 3 | 4 | 5 | 6 | 7 | [8] | 7 | 6 | 5 | 4 | 3 | 2 | 1 | [0] | 1 | [2] | 1 | 0 | -1 | -2 | -3 |

Index (cont.) | [24] | 25 | 26 | 27 | [28] | 29 | 30 |
---|---|---|---|---|---|---|---|

PingPong Value | [-4] | -3 | -2 | -1 | [0] | -1 | -2 |

Implement a function `pingpong`

that returns the nth element of the ping-pong
sequence *without using any assignment statements*. (You are allowed to use function definitions.)

You may use the function `num_eights`

, which you defined in the previous question.

**Important:**
Use recursion; the tests will fail if you use any assignment statements.
(You can however use function definitions if you so wish.)

Hint:If you're stuck, first try implementing`pingpong`

using assignment statements and a`while`

statement. Then, to convert this into a recursive solution, write a helper function that has a parameter for each variable that changes values in the body of the while loop.

Hint:There are a few pieces of information that we need to keep track of. One of these details is the direction that we're going (either increasing or decreasing). Building off of the hint above, think about how we can keep track of the direction throughout the calls to the helper function.

```
def pingpong(n):
"""Return the nth element of the ping-pong sequence.
>>> pingpong(8)
8
>>> pingpong(10)
6
>>> pingpong(15)
1
>>> pingpong(21)
-1
>>> pingpong(22)
-2
>>> pingpong(30)
-2
>>> pingpong(68)
0
>>> pingpong(69)
-1
>>> pingpong(80)
0
>>> pingpong(81)
1
>>> pingpong(82)
0
>>> pingpong(100)
-6
>>> from construct_check import check
>>> # ban assignment statements
>>> check(HW_SOURCE_FILE, 'pingpong',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr'])
True
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q pingpong`

### Q3: Count Coins

Given a positive integer `change`

, a set of coins makes change for `change`

if
the sum of the values of the coins is `change`

.
Here we will use standard US Coin values: 1, 5, 10, 25.
For example, the following sets make change for `15`

:

- 15 1-cent coins
- 10 1-cent, 1 5-cent coins
- 5 1-cent, 2 5-cent coins
- 5 1-cent, 1 10-cent coins
- 3 5-cent coins
- 1 5-cent, 1 10-cent coin

Thus, there are 6 ways to make change for `15`

. Write a **recursive** function
`count_coins`

that takes a positive integer `change`

and returns the number of
ways to make change for `change`

using coins.

You can use either of the functions given to you:

`next_larger_coin`

will return the next larger coin denomination from the input, i.e.`next_larger_coin(5)`

is`10`

.`next_smaller_coin`

will return the next smaller coin denomination from the input, i.e.`next_smaller_coin(5)`

is`1`

.- Either function will return
`None`

if the next coin value does not exist

There are two main ways in which you can approach this problem.
One way uses `next_larger_coin`

, and another uses `next_smaller_coin`

.

**Important:**
Use recursion; the tests will fail if you use loops.

Hint:Refer the implementation of`count_partitions`

for an example of how to count the ways to sum up to a final value with smaller parts. If you need to keep track of more than one value across recursive calls, consider writing a helper function.

```
def next_larger_coin(coin):
"""Returns the next larger coin in order.
>>> next_larger_coin(1)
5
>>> next_larger_coin(5)
10
>>> next_larger_coin(10)
25
>>> next_larger_coin(2) # Other values return None
"""
if coin == 1:
return 5
elif coin == 5:
return 10
elif coin == 10:
return 25
def next_smaller_coin(coin):
"""Returns the next smaller coin in order.
>>> next_smaller_coin(25)
10
>>> next_smaller_coin(10)
5
>>> next_smaller_coin(5)
1
>>> next_smaller_coin(2) # Other values return None
"""
if coin == 25:
return 10
elif coin == 10:
return 5
elif coin == 5:
return 1
def count_coins(change):
"""Return the number of ways to make change using coins of value of 1, 5, 10, 25.
>>> count_coins(15)
6
>>> count_coins(10)
4
>>> count_coins(20)
9
>>> count_coins(100) # How many ways to make change for a dollar?
242
>>> count_coins(200)
1463
>>> from construct_check import check
>>> # ban iteration
>>> check(HW_SOURCE_FILE, 'count_coins', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q count_coins`

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

Make sure to submit this assignment by uploading any files you've edited **to the appropriate Gradescope assignment.** For a refresher on how to do this, refer to Lab 00.

# Exam Practice

Homework assignments will also contain prior exam-level questions for you to take a look at. These questions have no submission component; feel free to attempt them if you'd like a challenge!

- Fall 2017 MT1 Q4a: Digital
- Summer 2018 MT1 Q5a: Won't You Be My Neighbor?
- Fall 2019 Final Q6b: Palindromes