A document from MCS 275 Spring 2021, instructor Emily Dumas. You can also get the notebook file.

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.

In [ ]:
# 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)
In [29]:
# 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.

In [33]:
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:

In [19]:
# 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)
In [36]:
# 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.

In [22]:
# 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)
In [26]:
[abbc(n) for n in range(16)]
Out[26]:
[0, 1, 2, 4, 9, 19, 41, 88, 189, 406, 872, 1873, 4023, 8641, 18560, 39865]

Revision history

  • 2021-02-23 Initial publication