This quiz must be submitted in Gradescope by 12:00pm CST on Tuesday, Februrary 23, 2021.
This quiz is about recursion.
Quizzes are INDIVIDUAL, closed book, and only allow access to specified resources. For this quiz you can access:
This quiz has 2 problems (numbered 2 and 3), each worth 4 points. Therefore, the final grading breakdown is:
| Points | Item |
|---|---|
| 3 | autograder |
| 4 | problem 2 |
| 4 | problem 3 |
| 11 | total |
The 3 points assigned by the autograder based on syntax and docstring checking will be listed as problem 1 in Gradescope.
The question given on the first version of the quiz I posted was more difficult than I intended, so everyone received 4 points on that problem.
Below you can find a discussion of the intended problem, the actual problem, and the solutions to both of them.
Let n be a positive integer. The pentafactorial of n is the product of all the positive integers that can be obtained by subtracting multiples of 5 from n.
Here are some examples:
pentafactorial(17) = 17 * 12 * 7 * 2 = 2856pentafactorial(10) = 10 * 5 = 50pentafacotrial(21) = 21*16*11*6*1 = 22176pentafactorial(6) = 6*1 = 6pentafactorial(5) = 5pentafactorial(4) = 4pentafactorial(3) = 3pentafactorial(2) = 2pentafactorial(1) = 1Write a recursive function named pentafactorial(n) that takes a positive integer n and returns its pentafactorial.
The key observation is that pentafactorial(n) = n * pentafactorial(n-5), with the base cases that pentafactorial(n)=n if n<=5.
# MCS 275 Quiz 6 Problem 2
# David Dumas
# I wrote this function following the rules in the quiz and the syllabus.
def pentafactorial(n):
"""Product of positive integers that can
be obtained by subtracting multiples of 5
from n"""
if n<=5:
return n
return n*pentafactorial(n-5)
# A test to make sure the given function reproduces the example values.
expected_vals = {
17: 2856,
10: 50,
21: 22176,
6: 6,
5: 5,
4: 4,
3: 3,
2: 2,
1: 1
}
for x in expected_vals:
y = pentafactorial(x)
if y == expected_vals[x]:
prefix = "OK: "
else:
prefix = "ERROR: "
print(prefix + "pentafactorial({}) = {}".format(x,y))
Here's what was actually written on the quiz when it was first released. (But to distinguish it from the function in the intended problem, in this version of the question I've changed the name to weird_pentafactorial.)
Let n be a positive integer. The weird pentafactorial of n is the integer obtained as follows:
n is less than 5, the weird pentafactorial of n is defined to be 1n is the product of all the positive integers that can be obtained by subtracting multiples of 5 from n.Here are some examples:
weird_pentafactorial(17) = 17 * 12 * 7 * 2 = 2856weird_pentafactorial(10) = 10 * 5 = 50weird_pentafacotrial(21) = 21*16*11*6*1 = 22176weird_pentafactorial(6) = 6*1 = 6weird_pentafactorial(5) = 5weird_pentafactorial(4) = 1weird_pentafactorial(3) = 1(Notice this is similar to factorial, but you move downward in steps of 5 instead of steps of 1.)
Write a recursive function named weird_pentafactorial(n) that takes a positive integer n and returns its weird pentafactorial.
What's strange about weird_pentafactorial(n) is that it is almost equal to n * weird_pentafactorial(n-5), but not quite. Consider weird_pentafactorial(8). According to the definition, that would be 8*3=24 because both 8 and 3 are positive integers that can be obtained by subtracting multiples of 5 from 8. However, 8*weird_pentafactorial(3) is equal to 8*1=8 because the definition says that weird_pentafactorial(3)=1.
The easiest way to handle this would be to just make a wrapper function that either gives 1 as an answer, or calls the "true pentafactorial" function defined earlier.
def weird_pentafactorial_first_attempt(n):
"""Product of positive integers that can
be obtained by subtracting multiples of 5
from n, with a weird special case for n<5"""
if n<5:
return 1
return pentafactorial(n)
# this call uses the function defined in the
# solution to the intended problem, above
However, this technically violates the conditions given in the question, which say "Write a recursive function". The function weird_pentafactorial_first_attempt above doesn't actually call itself, so it is not recursive. (Instead, it calls another function that is recursive.)
To actually do this recursively, I think the simplest way is to make a function that has an optional argument to indicate whether it is in a recursive call. The argument defaults to False, so that the function can apply the special rule for n<=5 when called by another part of the program. But when calling itself, it passes the optional argument with a value of True, making it use the pentafactorial behavior instead. Here's an implementation of that:
# MCS 275 Quiz 6 Problem 2
# David Dumas
# I wrote this function following the rules in the quiz and the syllabus.
def weird_pentafactorial(n,selfcall=False):
"""Product of positive integers that can
be obtained by subtracting multiples of 5
from n, with a weird special case for n<5"""
if n < 5:
if selfcall:
# To correctly handle n being a multiple of 5, we
# need to make it so that weird_pentafactorial(0,selfcall=True)
# returns 1. Otherwise we return n.
return max(n,1)
else:
return 1
return n*weird_pentafactorial(n-5,selfcall=True)
# A test to make sure the given function reproduces the example values.
weird_expected_vals = {
17: 2856,
10: 50,
21: 22176,
6: 6,
5: 5,
4: 1,
3: 1
}
for x in weird_expected_vals:
y = weird_pentafactorial(x)
if y == weird_expected_vals[x]:
prefix = "OK: "
else:
prefix = "ERROR: "
if y != expected_vals[x]:
# Make note of any case where weird_penta... and penta... differ
suffix = " (which is weird)"
else:
suffix = ""
print(prefix + "weird_pentafactorial({}) = {}".format(x,y) + suffix)
Define a sequence $Q$ of integers as follows: The first three values are
All subsequent terms are calculated by the following rule:
In other words, if the last three terms of the sequence you've computed are a, b, and c, then the next term is a+b+b+c.
The sequence therefore begins:
0, 1, 2, 4, 9, 19, 41, 88, 189, 406, 872, 1873, 4023, 8641, 18560, 39865Write a recursive function called abbc(n) that takes a nonnegative integer n and returns the value of $Q_n$. Save it in a file called quiz6prob3.py and include this file in your quiz submission.
# MCS 275 Quiz 6 Problem 3
# David Dumas
# I wrote this function following the rules in the quiz and the syllabus.
def abbc(n):
"""Sequence defined by Q_n = Q_{n-1}+2*Q_{n-2}+Q_{n-3}
and beginning 0,1,2 for n=0,1,2"""
if n<=2:
return n
return abbc(n-1) + 2*abbc(n-2) + abbc(n-3)
[abbc(n) for n in range(16)]