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:
Let's define a sequence of Great numbers $\{G_n\}_{n\geq0}$ as follows:
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.
# 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)
print("The 1st Great number is",great(1))
print("The 3rd Great number is",great(3))
print("The 10th Great number is",great(10))
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.
# 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)
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))
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,
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...
# 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.
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 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?
# 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
print(gcd(5,500))
print(gcd(17,83))
print(gcd(330,11))
print(gcd(360,240))
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
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:
Non-examples:
Write a recursive function is_palindrome_sandwich(s) which determines whether s is an palindrome sandwich.
When solving this problem, consider the following...
# 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
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"))
Next, a palindrome MULTIsandwich is a palindrome sandwich $AB\bar A$ where
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:
Nonexamples:
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.
# 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.
print(palindrome_multisandwich("racecarGO!racecar---racecar!OGracecar"))
print(palindrome_multisandwich("alexa---axela"))
print(palindrome_multisandwich("helloBYEolleh"))
print(palindrome_multisandwich("barkDOGbark"))
print(palindrome_multisandwich("laptop"))
Consider the following sequence...
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.)
# 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
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?
# 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
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))
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:
Encode your recursive sequence with a recursive function recursive(n).
# 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)
# 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...
Answers for the example recursive sequence.