Homework 3: Recursion, Tree Recursion
Due by 11:59pm on Thursday, September 22
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 with python3 ok
--submit
. 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 okpy.org. 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 pos
and
returns the number of times the digit 8 appears in pos
.
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(pos):
"""Returns the number of times 8 appears as a digit of pos.
>>> 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 awhile
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)
is10
.next_smaller_coin
will return the next smaller coin denomination from the input, i.e.next_smaller_coin(5)
is1
.- 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
Submit
Make sure to submit this assignment by running:
python3 ok --submit
Optional Contest
The following question is not worth any credit and is not a recursion problem. Instead, it is an optional fun contest that requires only knowledge of Midterm 1 concepts.
Q4: Busy Beaver Contest
The A+ question on the midterm discussed the concept of a Busy Beaver function, which is a function of a given length that tries to output as much as possible. During this question, starter code was provided to write a Beaver that ran f
64 times. In this question, you'll be able to write your own Busy Beaver function, and compete for the best Busy Beaver in the Busy Beaver contest! The rules for this contest are as follows:
Write a function beaver(f)
that takes in a function f
, and runs it as many times as possible. f
is a function that takes in 0 inputs, and outputs None
.
- Your code must be exactly one line long, and less than 100 characters long (not including trailing or leading whitespace)
- You may not use any numbers or strings, or any argument that evaluates to a number/string. This includes things like
int('1000')
, as this evaluates to a number and contains a string. - Your code must terminate (without crashing) in finite time.
- You may not import any functions, but may use built-in functions that do not need to be imported.
- You may not use semicolons.
There are two categories for this contest. For both categories, please adhere to the conditions outlined above.
For the first category, your solution should call
f
at least 1000 times. The goal of this category is to have a minimal-length line of code. That means, as long as your solution callsf
at least 1000 times, the only thing that matters is how short your solution is.- For this category, please write your code in
hw03.py
and runpython3 ok --submit
as usual to submit your solution. We will release rankings after all submissions have been processed. - If you would like to remain anonymous on the leaderboard, set the
anonymous
variable above the definition forbeaver
toTrue
. - Run the syntax checker (
python3 ok -q beaver_syntax_test
) to make sure your solution is one line. Runpython3 ok -q beaver_run_test
to check that your solution runs at least 1000 times.
- For this category, please write your code in
For the second category, your solution should call
f
as many times as possible, as long as your solution stays below the 100 character limit. Submit your solution, along with how many times you expect your solution to callf
, to this Google form.- For this category, you may assume that your code gets run on an ideal system with no memory or stack frame limits (so you may exceed the maximum recursion depth normally available in Python).
The deadline for the contest submission is the same as the rest of the homework, Thursday, September 22, 11:59pm.
anonymous = False # Change to True if you would like to remain anonymous on the final leaderboard.
def beaver(f):
"*** YOUR CODE HERE ***"
__________________
Use Ok to test your code:
python3 ok -q beaver_syntax_check
python3 ok -q beaver_run_test
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