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.
Test cases:
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.
print("The 1st Great number is",great(1), great_memo(1))
print("The 10th Great number is",great(10), great_memo(10))
print("The 50th Great number is",great(20), great_memo(20))
print("The 50th 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...
Test cases:
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?
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...
Test cases:
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.
Test cases:
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.)
Test cases:
print("Does Cantor set contain 15? ", cantor_dart_throw(15))
print("Does Cantor set contain 0? ", cantor_dart_throw(0.000000))
print("Does Cantor set contain 1/9? ", cantor_dart_attempt(1/9))
print("Does Cantor set contain 1/2? ", cantor_dart_attempt(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?
Test cases:
print("Does Cantor set contain 15? ", cantor_dart_attempt(15))
print("Does Cantor set contain 0.1? ", cantor_dart_attempt(0.1))
print("Does Cantor set contain 1/27? ", cantor_dart_attempt(1/27))
print("Does Cantor set contain 1/2? ", cantor_dart_attempt(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).
# Write your own test cases here! Check your base cases first, then a few cases that call the recursive step.
Next, without changing your recursive step, can you choose base cases $R_0$, ..., $R_{k-1}$ such that...
# Here's some test code to help you observe the values and ratios
# Prints values R_0, R_5, R_10, ..., R_100
for n in range(21):
r_5n = recursive(5*n)
print("recursive({}) = {}".format(5*n, r_5n))
# Prints ratios R_5/R_4, R_10/R_9, ..., R_100/R_99
r_n_minus_1 = recursive(0)
for n in range(1,21):
r_5n = recursive(5*n)
r_5n_minus_1 = recursive(5*n-1)
print("ratio ({}/{}) = {}".format(5*n, 5*n-1, r_5n/r_5n_minus_1))