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

Worksheet 6 Solutions

MCS 275 Spring 2021 - Emily Dumas

Worksheet and Solutions by Jennifer Vaccaro

Instructions:

In your breakout room groups, read the instructions for the following problems and write the functions/scripts to solve them. Each problem has multiple parts, where the first step involves writing a recursive function, and later parts involve modifying the function to highlight features of recursive functions and sequences. Depending on time, you may wish to complete all of problem 1, the first parts of 2-5, and then the second parts of whichever 2-5 you found most interesting.

Some problems involve counting recursive steps, tracking function runtime, or memoization. Here is a decorator module that you may download and import to help implement these features.

Here are links to relevant recent lectures:

1. Great sequence and decorators

Let's define a sequence of Great numbers $\{G_n\}_{n\geq0}$ as follows:

  • Base cases: $G_0 = 1$, $G_1 = 3$, $G_2 = 5$
  • Recursive step: $G_n = G_{n-1} - 3*G_{n-3}$

So the first several Great numbers are 1,3,5,2,-7,-22,-28,-8.

Write a function great(n) that calculates the nth Great number recursively. That is, the function great should call itself for some inputs n.

In [1]:
# MCS 275 Week 6 Problem 1
# Jennifer Vaccaro
# I developed this solution myself, in accordance with the rules in the syllabus.

def great(n):
    """Recursive function returning the nth number from the 
    Great sequence"""
    # Base cases G_0, G_1, and G_2
    if n==0:
        return 1
    if n==1:
        return 3
    if n == 2:
        return 5
    # Recursive step if n > 2, which uses previous G values
    return great(n-1) - 3*great(n-3)
In [2]:
print("The 1st Great number is",great(1))
print("The 3rd Great number is",great(3))
print("The 10th Great number is",great(10))
The 1st Great number is 3
The 3rd Great number is 2
The 10th Great number is 164

For the second part of this problem, you will use memoization. Memo-izing a function allows you to "save" previous pairs of inputs and outputs as base cases, so you can use less recursive depth.

For example, suppose you calculate great(3) and then calculate great(6). Fince $G_6$ = $G_5$ - 3*$G_3$, and you have already calculated $G_3$, your function could incorporate the previously calculated value as a base case.

Write another function great_memo(n) that uses the memoization decorator from decs.py. Compare the performance of both great functions for inputs 1,10,20,30.

In [3]:
# MCS 275 Week 6 Problem 1
# Jennifer Vaccaro
# I developed this solution myself, in accordance with the rules in the syllabus.

import decs # Use the professor's decorator module.

@decs.memoize # This decorator stores recent input/output pairs in a dictionary, so essentially adds all previously calculated great numbers as base cases.
def great_memo(n):
    """Calculates the nth Great number, and caches the result to reduce recursive depth."""
    # Same logic as great(n)
    if n==0:
        return 1
    if n==1:
        return 3
    if n == 2:
        return 5
    return great_memo(n-1) - 3*great_memo(n-3)
In [4]:
print("The 1st Great number is",great(1), great_memo(1))
print("The 10th Great number is",great(10), great_memo(10))
print("The 20th Great number is",great(20), great_memo(20))
print("The 30th Great number is",great(30), great_memo(30))
The 1st Great number is 3 3
The 10th Great number is 164 164
The 20th Great number is -22828 -22828
The 30th Great number is -124723 -124723

2. Prime Factorization

A prime number is an integer whose only divisors are 1 and itself. Primes include $2,3,5,7,11,...$

By the Fundamental Theorem of Algebra, every positive integer $n\geq 2$ can be factored into a product of primes. The collection of primes is called the unique prime factorization, since it is unique up to reordering.

For example,

  • $ 10 = 2*5$
  • $ 30 = 2*3*5$
  • $ 45 = 3*3*5$
  • $ 64 = 2*2*2*2*2*2$ (Note that the same prime may appear multiple times.)

Write a recursive function pf(n) that, given an integer $n \geq 2$, returns a list representing the prime factorization. Note that the list can contain the same prime repeated multiple times.

When solving this problem, consider the following...

  • What are the base cases? (For what inputs will pf(n) return a list with one entry?)
  • What is the recursive step? (How do we break pf(n) into pieces which incorporate pf called on a smaller input?)
In [5]:
# MCS 275 Week 6 Problem 2
# Jennifer Vaccaro
# I developed this solution myself, in accordance with the rules in the syllabus.

def pf(n):
    """Returns the prime factorization of a positive integer n"""
    if n==0 or n==1:
        return [] # If n < 2, then n has no prime factors.
    for i in range(2,n): # Check each integer up to n
        if n % i == 0:  # if i divides n evenly, then i is a prime factor of n. This is because if i is composite, then we would reach a factor of i before checking i. So only prime factors would satisfy this conditional.
            return pf(n//i) + [i] #return the prime factorization of the integer quotient.
    return [n] # The "base case" is that n is prime.
In [6]:
print("The prime factorization of 15 is", pf(15))
print("The prime factorization of 81 is", pf(81))
print("The prime factorization of 17 is", pf(17))
The prime factorization of 15 is [5, 3]
The prime factorization of 81 is [3, 3, 3, 3]
The prime factorization of 17 is [17]

The greatest common denominator $gcd(a,b)$ is the largest integer that evenly divides both $a$ and $b$. One way to calculate the gcd is to use the product of all common prime factors of $a$ and $b$. If $a$ and $b$ share no prime factors, then $gcd(a,b) = 1$.

Write a function gcd(a,b) that calculates the greatest common divisor and calls your function pf. (The function does not need to be recursive.)

As an added challenge, can you improve the performance of pf and gcd using memoization?

In [7]:
# MCS 275 Week 6 Problem 2
# Jennifer Vaccaro
# I developed this solution myself, in accordance with the rules in the syllabus.

def gcd(a,b):
    """Returns the gcd of two positive integers a and b using the
    product of their shared factors."""
    gcd_ab = 1 # If they share no prime factors, then gcd(a,b)==1
    b_factors = pf(b)
    for f in pf(a): # Check each factor f of a
        if f in b_factors: # Check if f is also a factor of b
            gcd_ab *= f # multiply gcd_ab by f
            b_factors.pop(b_factors.index(f)) # Remove the factor from b_factors, so that it isn't double counted when matched with factors of a
    return gcd_ab
In [8]:
print(gcd(5,500))
print(gcd(17,83))
print(gcd(330,11))
print(gcd(360,240))
5
1
11
120

3. Palindrome Sandwiches

A palindrome is a string that is the same forwards and backwards.

A palindrome sandwich is a string of the form $AB\bar A$ where

  • $A$ is a string
  • $B$ is a string of length 3, and
  • $\bar A$ is $A$ backwards.

That is to say $A\bar A$ is a palindrome, but $A$, $B$ and $\bar A$ need not be palindromes. $A$ and $\bar A$ must be non-empty, so the shortest palindrome sandwich has length 5.

Examples:

  • "racecar" is a palindrome sandwich where $A$="ra", $B$="cec", and $\bar A$="ar".
  • "noHATon" is a palindrome sandwich where $A$="no", $B$="HAT", and $\bar A$="on".

Non-examples:

  • "goodBYEgood" is NOT a palindrome sandwich, since "good" is not "good" backwards.
  • "squirrel" is NOT an palindrome sandwich, since it does not have odd length.

Write a recursive function is_palindrome_sandwich(s) which determines whether s is an palindrome sandwich.

When solving this problem, consider the following...

  • How do you isolate $A$, $B$, and $\bar A$?
  • What would be the base case?
  • What would be the recursive step?
In [9]:
# MCS 275 Week 6 Problem 3
# Jennifer Vaccaro
# I developed this solution myself, in accordance with the rules in the syllabus.

def is_palindrome_sandwich(s):
    """Using recursion, checks that s is a palindrome sandwich, that is, that s=A+B+~A where
    A is a string
    B has length 3
    ~A is A backwards."""
    len_s = len(s)
    if len_s < 5 or len_s % 2 == 0:
        return False # Base case: If even length of length <5, return False
    if s[0] == s[-1]:
        if len_s == 5:
            return True # Base case: is a string aBa, return True
        return is_palindrome_sandwich(s[1:-1]) # If length odd and >5, check if the inner string is a palindrome sandwich.
    return False # if s[0] != s[-1], return False
In [10]:
print(is_palindrome_sandwich("racecar"))
print(is_palindrome_sandwich("noHATon"))
print(is_palindrome_sandwich("racecarCATracecar"))
print(is_palindrome_sandwich("goodBYEgood"))
print(is_palindrome_sandwich("squirrel"))
True
True
True
False
False

Next, a palindrome MULTIsandwich is a palindrome sandwich $AB\bar A$ where

  • $A$ is a string or a palindrome sandwich
  • $B$ is a string of length 3
  • $\bar A$ is $A$ backwards. (If $A$ is a palindrome sandwich, then so is $\bar A$.)

The "level" of the multisandwich is the number of nested palindrome sandwiches. Non-sandwiches have level 0, and "simple" palindrome sandwiches have level 1.

Examples:

  • "racecarGO!racecar" has level 2, since "racecar"+"GO!"+"racecar" is a palindrome sandwich, and "ra"+"cec"+"ar" is also a palindrome sandwich, but "ra" is not a palindrome sandwich since it has length less than 5.
  • "alexa---axela" has level 2, since "alexa"+"---"+"alexa" is a palindrome sandwich and "a"+"lex"+"a" is also a palindrome sandwich, but "a" is not a palindrome sandwich since it has length less than 5.
  • "helloBYEolleh" has level 1, since "hello"+"BYE"+"olleh" is a palindrome sandwich, but "h"+"ell"+"o" is not a palindrome sandwich since "h"!="o".

Nonexamples:

  • "barkDOGbark" is NOT a palindrome sandwich, so it has level 0.
  • "laptop" is NOT a palindrome sandwich, so it has level 0.

Write a recursive function palindrome_multisandwich(s) which determines whether s is a palindrome multisandwich, and what level it is. It should first check whether s is a palindrome sandwich, then whether $A$ is a palindrome sandwich, and so on. The function should return an integer, with 0 representing "not a palindrome sandwich", 1 representing a "simple" palindrome sandwich, etc.

This function may call is_palindrome_sandwich from the previous part. Once again, first define the base case and the recursive step.

In [11]:
# MCS 275 Week 6 Problem 3
# Jennifer Vaccaro
# I developed this solution myself, in accordance with the rules in the syllabus.

def palindrome_multisandwich(s):
    """Returns the number of nested palindrome sandwiches of s"""
    if not is_palindrome_sandwich(s):
        return 0 # Base case is s NOT a palindrome sandwich
    # If a is a palindrom sandwich, then isolate the block for A and check that
    len_A = (len(s)-3)//2
    A = s[:len_A]
    return 1 + palindrome_multisandwich(A) # recursive step is checking the multisandwich level of A, and adding 1 since s is a sandwich.
In [12]:
print(palindrome_multisandwich("racecarGO!racecar---racecar!OGracecar"))
print(palindrome_multisandwich("alexa---axela"))
print(palindrome_multisandwich("helloBYEolleh"))
print(palindrome_multisandwich("barkDOGbark"))
print(palindrome_multisandwich("laptop"))
3
2
1
0
0

4. Cantor set darts

Consider the following sequence...

  • $C_0 = [0,1]$ the closed interval from 0 to 1
  • $C_1 = [0,1/3] \cup [2/3, 1]$ the union of two closed intervals
  • $C_2 = [0,1/9] \cup [2/9,1/3] \cup [2/3,7/9] \cup [8/9,1]$ the union of four closed intervals
  • $C_n = [0,(1/3)^{n}] \cup ... \cup [1-(1/3)^{n},1]$ the union of $2^{n}$ closed intervals

Then the 2/3 Cantor set is the intersection of all $C_n$ from $n=0$ to infinity. Here is a link for more information about the Cantor set.

Your goal is to write a recursive function cantor_dart_throw(x) that, given a float input x, returns True or False whether x is in the Cantor set.

(Suggestion: Define a default argument "interval=None". Within the function, check if interval is None, and in that case set interval=[0,1]. If x is outside interval, or in the middle third, return False. If x is inside the the 1st or 3rd third and within 4 decimal places of an interval endpoint, return True. Otherwise, return cantor_dart_throw(x, new_interval) with new_interval defined as the appropriate third.)

In [13]:
# MCS 275 Week 6 Problem 4
# Jennifer Vaccaro
# I developed this solution myself, in accordance with the rules in the syllabus.

def cantor_dart_throw(x,interval=None, calls=1):
    """Recursively checks whether x is in the Cantor set."""
    if interval == None:
        interval = [0,1]
    start = interval[0]
    end = interval[1]
    if x<start or x>end:
        return False # Base case, x outside the interval ==> False
    one_third = start + (end-start)*1/3
    two_third = start + (end-start)*2/3
    if x>=start and x<=one_third:
        if x-start < 10**-5: # x "float equals" start
            return True
        return cantor_dart_throw(x,[start,one_third]) # check x on the new interval
    if x>one_third and x<two_third:
        return False # Base case, x in middle third ==> False
    if x>=two_third and x<=end:
        if end-x < 10**-5: # x "float equals" end
            return True
        return cantor_dart_throw(x,[two_third,end]) # Check x on the new interval
In [14]:
print("Does Cantor set contain 15? ", cantor_dart_throw(15))
print("Does Cantor set contain 0?", cantor_dart_throw(0))
print("Does Cantor set contain 1/9?", cantor_dart_throw(1/9))
print("Does Cantor set contain 1/2?", cantor_dart_throw(1/2))

For second part of this problem, you will want to determine how many recursive steps were required to get you an answer of True/False. You can modify cantor_dart_throw to use the count_calls decorator from decs.py.

Then, find an input x that requires at least 10 calls. Can you find one that returns True and one that returns False? What is the maximum depth of recursion possible in your program?

In [ ]:
# MCS 275 Week 6 Problem 4
# Jennifer Vaccaro
# I developed this solution myself, in accordance with the rules in the syllabus.

def cantor_dart_throw(x,interval=None, calls=1): # pass the interval and call count down.
    """Recursively checks whether x is in the Cantor set, and prints out the number of calls that were made before returning."""
    if interval == None:
        interval = [0,1]
    start = interval[0]
    end = interval[1]
    if x<start or x>end:
        print("CALLS:",calls)
        return False # Base case, x outside the interval ==> False
    one_third = start + (end-start)*1/3
    two_third = start + (end-start)*2/3
    if x>=start and x<=one_third:
        if x-start < 10**-5: # x "float equals" start
            print("CALLS:",calls)
            return True
        return cantor_dart_throw(x,[start,one_third], calls+1) # check x on the new interval
    if x>one_third and x<two_third:
        print("CALLS:",calls)
        return False # Base case, x in middle third ==> False
    if x>=two_third and x<=end:
        if end-x < 10**-5: # x "float equals" end
            print("CALLS:",calls)
            return True
        return cantor_dart_throw(x,[two_third,end], calls+1) # Check x on the new interval
In [ ]:
print("Does Cantor set contain 15? ", cantor_dart_throw(15))
print("Does Cantor set contain 0.1? ", cantor_dart_throw(0.1))
print("Does Cantor set contain 1/27? ", cantor_dart_throw(1/27))
print("Does Cantor set contain 1/2? ", cantor_dart_throw(1/2))

5. Create your own recursive sequence

Consider the Fibonacci sequence $F_n$ defined in a lecture example, or the Great number sequence $G_n$ defined in Problem 1.

Create a numerical recursive sequence $R_n$ using the following rules:

  • $R_n$ is a sequence defined on all $n\geq 0$
  • Define several base cases $R_0$, ..., $R_{k-1}$ with $k\geq3$
  • Define your recursive step. $R_n$ should be calculated based on at least 3 previous steps within the range of your $k$ base cases. You can add, multiply, subtract, etc.

Encode your recursive sequence with a recursive function recursive(n).

In [ ]:
# MCS 275 Week 6 Problem 5
# Jennifer Vaccaro
# I developed this solution myself, in accordance with the rules in the syllabus.

def recursive(n):
    """Returns the nth value of a recursive sequence where...
    R_0 = 1
    R_1 = 1
    R_2 = 1
    R_n = R_{n-1} + R_{n-2} + R_{n-3}
    Note: your recursive sequence may look different, but it should have base cases and a recursive step."""
    # Base cases
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 1
    # Recursive step
    return recursive(n-1) + recursive(n-2) + recursive(n-3)
In [2]:
# Write your own test cases here! Check your base cases first, then a few cases that call the recursive step.
print(recursive(0))
print(recursive(1))
print(recursive(2))
print(recursive(5))

Next, without changing your recursive step, can you choose base cases $R_0$, ..., $R_{k-1}$ such that...

  • For $n=0,1,...,100$, $R_n$ appears to approach positive infinity.
  • For $n=0,1,...,100$, $R_n$ appears to approach negative infinity.
  • Within $n=0,1,...,100$, $R_n$ has a cycle of size $k$ or greater.
  • For $n=0,1,...,100$, the ratio $R_n / R_{n+1}$ appears to approach a constant value.

Answers for the example recursive sequence.

  • With the values $R_0=1, R_1=1, and R_2=1, R_n$ approaches positive infinity.
  • With the values $R_0=-1, R_1=-1, and R_2=-1, R_n$ approaches negative infinity.
  • With the values $R_0=2, R_1=-4, R_2=2$ has a cycle of length 6, which is greater than 3.
  • With the values $R_0=1, R_1=1, and R_2=1,$ the ratio $R_n/R_{n+1}$ approaches ~0.543689.
In [ ]: