Quiz 6 Solutions¶

MCS 275 Spring 2021 - Emily Dumas¶

Instructions:¶

Deadline¶

This quiz must be submitted in Gradescope by 12:00pm CST on Tuesday, Februrary 23, 2021.

Topic¶

This quiz is about recursion.

Resources you are allowed to consult¶

Quizzes are INDIVIDUAL, closed book, and only allow access to specified resources. For this quiz you can access:

Point distribution¶

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

(No problem number 1, as usual)¶

The 3 points assigned by the autograder based on syntax and docstring checking will be listed as problem 1 in Gradescope.

Problem 2 deleted¶

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.

Problem 2 as it should have been: Pentafactorial¶

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 = 2856
pentafactorial(10) = 10 * 5 = 50
pentafacotrial(21) = 21*16*11*6*1 = 22176
pentafactorial(6) = 6*1 = 6
pentafactorial(5) = 5
pentafactorial(4) = 4
pentafactorial(3) = 3
pentafactorial(2) = 2
pentafactorial(1) = 1

Write a recursive function named pentafactorial(n) that takes a positive integer n and returns its pentafactorial.

Solution to Problem 2 as it should have been¶

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

OK: pentafactorial(17) = 2856
OK: pentafactorial(10) = 50
OK: pentafactorial(21) = 22176
OK: pentafactorial(6) = 6
OK: pentafactorial(5) = 5
OK: pentafactorial(4) = 4
OK: pentafactorial(3) = 3
OK: pentafactorial(2) = 2
OK: pentafactorial(1) = 1

Problem 2 as originally written: Pentafactorial¶

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:

If n is less than 5, the weird pentafactorial of n is defined to be 1
Otherwise, the weird 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:

weird_pentafactorial(17) = 17 * 12 * 7 * 2 = 2856
weird_pentafactorial(10) = 10 * 5 = 50
weird_pentafacotrial(21) = 21*16*11*6*1 = 22176
weird_pentafactorial(6) = 6*1 = 6
weird_pentafactorial(5) = 5
weird_pentafactorial(4) = 1
weird_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.

Solution to Problem 2 as originally written¶

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

OK: weird_pentafactorial(17) = 2856
OK: weird_pentafactorial(10) = 50
OK: weird_pentafactorial(21) = 22176
OK: weird_pentafactorial(6) = 6
OK: weird_pentafactorial(5) = 5
OK: weird_pentafactorial(4) = 1 (which is weird)
OK: weird_pentafactorial(3) = 1 (which is weird)

Problem 3: abbc sequence¶

Define a sequence $Q$ of integers as follows: The first three values are

$Q_0 = 0$
$Q_1 = 1$
$Q_2 = 2$

All subsequent terms are calculated by the following rule:

$Q_n = Q_{n-1} + 2 Q_{n-2} + Q_{n-3}$

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, 39865

Write 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
# Emily 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)]

[0, 1, 2, 4, 9, 19, 41, 88, 189, 406, 872, 1873, 4023, 8641, 18560, 39865]

Revision history¶

2021-02-23 Initial publication