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

Worksheet 6

MCS 275 Spring 2021 - Emily Dumas

Worksheet 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.

Test cases:

In [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))
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 [6]:
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))
The 1st Great number is 3 3
The 10th Great number is 164 164
The 50th Great number is -22828 -22828
The 50th 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?)

Test cases:

In [29]:
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 [34]:
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?

Test cases:

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

Test cases:

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

Test cases:

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

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

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 [2]:
# 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...

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