Lab 3 Solutions
Solution Files
Topics
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Recursion
A recursive function is a function that calls itself in its body, either directly or indirectly.
Let's look at the canonical example, factorial
.
Factorial, denoted with the
!
operator, is defined as:n! = n * (n-1) * ... * 1
For example,
5! = 5 * 4 * 3 * 2 * 1 = 120
The recursive implementation for factorial is as follows:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
We know from its definition that 0! is 1. Since n == 0
is the smallest number we
can compute the factorial of, we use it as our base case.
The recursive step also follows from the definition of factorial, i.e., n! =
n * (n-1)!
.
Recursive functions have three important components:
Base case. You can think of the base case as the case of the simplest function input, or as the stopping condition for the recursion.
In our example,
factorial(0)
is our base case for thefactorial
function.Recursive call on a smaller problem. You can think of this step as calling the function on a smaller problem that our current problem depends on. We assume that a recursive call on this smaller problem will give us the expected result; we call this idea the "recursive leap of faith".
In our example,
factorial(n)
depends on the smaller problem offactorial(n-1)
.Solve the larger problem. In step 2, we found the result of a smaller problem. We want to now use that result to figure out what the result of our current problem should be, which is what we want to return from our current function call.
In our example, we can compute
factorial(n)
by multiplying the result of our smaller problemfactorial(n-1)
(which represents(n-1)!
) byn
(the reasoning being thatn! = n * (n-1)!
).
The next few questions in lab will have you writing recursive functions. Here are some general tips:
- Paradoxically, to write a recursive function, you must assume that the function is fully functional before you finish writing it; this is called the recursive leap of faith.
- Consider how you can solve the current problem using the solution to a simpler version of the problem. The amount of work done in a recursive function can be deceptively little: remember to take the leap of faith and trust the recursion to solve the slightly smaller problem without worrying about how.
- Think about what the answer would be in the simplest possible case(s). These will be your base cases - the stopping points for your recursive calls. Make sure to consider the possibility that you're missing base cases (this is a common way recursive solutions fail).
- It may help to write an iterative version first.
Tree Recursion
A tree recursive function is a recursive function that makes more than one call to itself, resulting in a tree-like series of calls.
For example, this is the Virahanka-Fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, ...
.
Each term is the sum of the previous two terms. This tree-recursive function calculates the n
th Virahanka-Fibonacci number.
def virfib(n):
if n == 0 or n == 1:
return n
return virfib(n - 1) + virfib(n - 2)
Calling virfib(6)
results in a call structure that resembles
an upside-down tree (where f
is virfib
):
Each recursive call f(i)
makes a call to f(i-1)
and a call to f(i-2)
.
Whenever we reach an f(0)
or f(1)
call, we can directly return 0
or 1
without making more recursive calls. These calls are our base cases.
A base case returns an answer without depending on the results of other calls. Once we reach a base case, we can go back and answer the recursive calls that led to the base case.
As we will see, tree recursion is often effective for problems with branching choices. In these problems, you make a recursive call for each branching choice.
Required Questions
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). Do not use for
or while
.
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.
def double_eights(n):
""" Returns whether or not n has two digits in row that
are the number 8. Assume n has at least two digits in it.
>>> double_eights(1288)
True
>>> double_eights(880)
True
>>> double_eights(538835)
True
>>> double_eights(284682)
False
>>> double_eights(588138)
True
>>> double_eights(78)
False
>>> from construct_check import check
>>> # ban iteration
>>> check(LAB_SOURCE_FILE, 'double_eights', ['While', 'For'])
True
"""
last, second_last = n % 10, n // 10 % 10
if last == 8 and second_last == 8:
return True
elif n < 100:
return False
return double_eights(n // 10)
# Alternate solution
last, second_last = n % 10, n // 10 % 10
if n < 10:
return False
return (last == 8 and second_last == 8) or double_eights(n // 10)
# Alternate solution with helper function:
def helper(num, prev_eight):
if num == 0:
return False
if num % 10 == 8:
if prev_eight:
return True
return helper(num // 10, True)
return helper(num // 10, False)
return helper(n, False)
Use Ok to test your code:
python3 ok -q double_eights
Q2: Making Onions
Write a function make_onion
that takes in two one-argument functions, f
and
g
. It returns a function that takes in three arguments: x
, y
, and
limit
. The returned function returns True
if it is possible to reach y
from x
using up to limit
calls to f
and g
, and False
otherwise.
For example, if f
adds 1 and g
doubles, then it is possible to reach 25 from
5 in four calls: f(g(g(f(5))))
.
def make_onion(f, g):
"""Return a function can_reach(x, y, limit) that returns
whether some call expression containing only f, g, and x with
up to limit calls will give the result y.
>>> up = lambda x: x + 1
>>> double = lambda y: y * 2
>>> can_reach = make_onion(up, double)
>>> can_reach(5, 25, 4) # 25 = up(double(double(up(5))))
True
>>> can_reach(5, 25, 3) # Not possible
False
>>> can_reach(1, 1, 0) # 1 = 1
True
>>> add_ing = lambda x: x + "ing"
>>> add_end = lambda y: y + "end"
>>> can_reach_string = make_onion(add_ing, add_end)
>>> can_reach_string("cry", "crying", 1) # "crying" = add_ing("cry")
True
>>> can_reach_string("un", "unending", 3) # "unending" = add_ing(add_end("un"))
True
>>> can_reach_string("peach", "folding", 4) # Not possible
False
"""
def can_reach(x, y, limit):
if limit < 0:
return False elif x == y:
return True else:
return can_reach(f(x), y, limit - 1) or can_reach(g(x), y, limit - 1) return can_reach
Use Ok to test your code:
python3 ok -q make_onion
Tree Recursion
Q3: Super Mario
Mario needs to jump over a sequence of Piranha plants called level
. level
is represented as a string of empty spaces (' '
), indicating no plant, and P's ('P'
), indicating the presence of a plant. Mario only moves forward and can either step (move forward one spot) or jump (move forward two spots) from each position. How many different ways can Mario traverse a level
without stepping or jumping into a Piranha plant ('P'
)? Assume that every level
begins with an empty space (' '
), where Mario starts, and ends with an empty space (' '
), where Mario must end up.
Hint: You can access the ith character in a string
s
by usings[i]
. For example:>>> s = 'abcdefg' >>> s[0] 'a' >>> s[2] 'c'
Hint: You can find the total number of characters in a string using the built-in
len
function:>>> s = 'abcdefg' >>> len(s) 7 >>> len('') 0
def mario_number(level):
"""Return the number of ways that Mario can perform a sequence of steps
or jumps to reach the end of the level without ever landing in a Piranha
plant. Assume that every level begins and ends with a space.
>>> mario_number(' P P ') # jump, jump
1
>>> mario_number(' P P ') # jump, jump, step
1
>>> mario_number(' P P ') # step, jump, jump
1
>>> mario_number(' P P ') # step, step, jump, jump or jump, jump, jump
2
>>> mario_number(' P PP ') # Mario cannot jump two plants
0
>>> mario_number(' ') # step, jump ; jump, step ; step, step, step
3
>>> mario_number(' P ')
9
>>> mario_number(' P P P P P P P P ')
180
"""
def ways(n):
if n == len(level)-1:
return 1
if n >= len(level) or level[n] == 'P':
return 0
return ways(n+1) + ways(n+2)
return ways(0)
Use Ok to test your code:
python3 ok -q mario_number
Q4: Maximum Subsequence
A subsequence of a number is a series of digits from the number (not necessarily contiguous). For example, 12345 has subsequences like 123, 234, 124, 245, etc. Your task is to find the largest subsequence that is under a specified length.
Hint: To add a digit (
d
) to an existing number (n
), calculate:n * 10 + d
. For instance, to add8
to15
to get158
, compute15 * 10 + 8
.
def max_subseq(n, t):
"""
Return the maximum subsequence of length at most t that can be found in the given number n.
For example, for n = 2012 and t = 2, we have that the subsequences are
2
0
1
2
20
21
22
01
02
12
and of these, the maxumum number is 22, so our answer is 22.
>>> max_subseq(2012, 2)
22
>>> max_subseq(20125, 3)
225
>>> max_subseq(20125, 5)
20125
>>> max_subseq(20125, 6) # note that 20125 == 020125
20125
>>> max_subseq(12345, 3)
345
>>> max_subseq(12345, 0) # 0 is of length 0
0
>>> max_subseq(12345, 1)
5
"""
if n == 0 or t == 0:
return 0
with_last = max_subseq(n // 10, t - 1) * 10 + n % 10
without_last = max_subseq(n // 10, t)
return max(with_last, without_last)
Use Ok to test your code:
python3 ok -q max_subseq
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.
In addition, all students who are not in the mega lab must submit the attendance form for credit. Ask your section TA for the link! Submit this form for each section, whether you attended lab or missed it for a good reason. The attendance form is not required for mega section students.
Optional Questions
Q5: Recursive Prime
Below is the iterative version of is_prime
, which returns True
if positive
integer n
is a prime number and False
otherwise:
def is_prime(n):
if n == 1:
return False
k = 2
while k < n:
if n % k == 0:
return False
k += 1
return True
Implement the recursive is_prime
function. Do not use a while loop, use recursion.
As a reminder, an integer is considered prime if it has exactly two unique factors: 1 and itself.
def is_prime(n):
"""
>>> is_prime(7)
True
>>> is_prime(10)
False
>>> is_prime(1)
False
"""
def prime_helper(index):
if index == n:
return True
elif n % index == 0 or n == 1:
return False
else:
return prime_helper(index + 1)
return prime_helper(2)
Use Ok to test your code:
python3 ok -q is_prime