The main topics of this worksheet is recursion.
The other worksheet from this course that focuses on recursion is here.
These things might be helpful while working on the problems. Remember that for worksheets, we don't strictly limit what resources you can consult, so these are only suggestions.
There is a sequence of integers $T_n$ defined by the conditions
$$\begin{split} T_0 &= 0\\ T_1 &= 1\\ T_2 &= 2\\ T_{n} &= T_{n-1} + T_{n-2} + T_{n-3} \text{ if } n \geq 3\end{split}$$This sequence begins $0, 1, 2, 3, 6, 11, 20, 37, 68, 125, 230, 423, 778, 1431, 2632, \ldots$.
Write a recursive function that calculates $T_n$.
Then, determine the rule that describes the sequence whose $n^{\text{th}}$ term is the number of function calls that occur in calculating $T_n$.
import decs # decs.py module from MCS 275 Github in folder: /samplecode/recursion/
@decs.count_calls
def T(n):
'''Calculates T_n recursively'''
if n <= 2:
return n
else:
return T(n-1) + T(n-2) + T(n-3)
print("T(20)={}".format(T(20)))
print("{} calls were made when calculating T(20)".format(decs.get_call_count("T")))
def num_calls_to_T(n):
'''Returns number of calls made to function T when calculating T(n)'''
if n <= 2:
return 1 # The base cases always make 1 additional call to T(n)
else:
# When making a recursive call, add 1 to account for the current call to T
# (Note that the calls from T(n-1), T(n-2), T(n-3) are already counted)
return num_calls_to_T(n-1) + num_calls_to_T(n-2) + num_calls_to_T(n-3) + 1
print("{} calls were made when calculating T(20)".format(num_calls_to_T(20)))
An integer greater than 1 is called prime if its only divisors are 1 and itself.
The Fundamental Theorem of Algebra states that every positive integer other than 1 is a product of primes, and that the description as a product of primes is unique up to reordering the factors. For example, $275$ can be expressed as $5\times5\times11$.
Write a recursive function factor(n) that takes an integer n greater than 1 and returns a list of primes whose product is equal to n. That is, factor(n) returns the prime factorization of n.
I recommend the following strategy: Try to find a way to express n as a product of two other integers greater than 1. If you fail, you know that n is prime. If you succeed, you the have n = k * m and so it would be enough to know the prime factorization of k and of m.
Hint: One way to check whether k divides n, is to check whether the remainder n%k is zero.
Acknowledgement: This problem is based in part on a problem on a 2021 MCS 275 worksheet by Jennifer Vaccaro.
The count_calls decorator from the decsmodule (Github link) is used here so that we can compare the number of calls in Question 4 later in the worksheet.
Note: When running on a notebook (e.g. Jupyter or Colab), the number of calls made to a specific function won't reset when running cells multiple times. One way to reset this is to reset the kernel.
@decs.count_calls
def factor(n):
'''Returns list of prime factors of `n`'''
if n==0 or n==1:
return [] # If n < 2, then n has no prime factors.
for k in range(2,n): # Check each integer from 2 to n-1
if n % k == 0: # In this case, we have n = k * m for some other integer m
m = int(n / k)
# Here, `+` is used to add two lists (i.e. append one list to the other)
return factor(k) + factor(m)
return [n] # If no factors of `n` are found, then it is prime, so it cannot be factored
print("The prime factors of 32768 are: {}".format(factor(32768))) # 1024 is 2^15
print("{} calls were made when calculating factors of 32768".format(decs.get_call_count("factor")))
print("The prime factors of 275 are: {}".format(factor(275)))
There are lots of ways to put parentheses in the algebraic expression a+b+c+d so that every application of + becomes a binary operation. For example:
((a+b)+(c+d))(a+(b+(c+d)))Write a Python function that takes a list of variables or numbers to be summed, and returns all possible ways of parenthesizing the sum fully.
This requires a choice of how to represent the input sum and output parenthesized sums. Instead of using strings, make your function so it expects a list of summands as input and returns a list of possible parenthesized versions that use nested Python lists to represent the parentheses.
The return value is a list of length 5, which means there are five ways, described by the nested list structure of one of the items in the return value. These represent:
(2+(1+(5+8)))
(2+((1+5)+8))
(2+1)+(5+8)
((2+(1+5))+8)
(((2+1)+5)+8)def put_parens(summands):
'''Takes a list `summands` and recursively places parentheses in all possible configurations'''
if len(summands) == 1: # No way to put parentheses
return summands
elif len(summands) == 2: # Only one way to put parentheses
return [summands]
else:
L = []
for i in range(1,len(summands)):
for first in put_parens(summands[:i]): # Find all places to open a parenthesis
for second in put_parens(summands[i:]): # Find all places to close a parenthesis
L.append([first,second])
return L
put_parens([2,1,5,8]) # find all ways to put parentheses in the expression 2+1+5+8
Make versions of the recursive functions from problems 1 and 2 that use memoization to attempt to improve their efficiency.
Do they benefit significantly from this modification? Does one benefit more than the other?
T:¶cache = {0: 0,
1: 1,
2: 2} # Save the base cases in the cache
@decs.count_calls
def T_memoized(n):
'''Calculates T_n recursively'''
# We don't need the base cases anymore since we put them in the cache
# This list will be filled with 3 entries: T(n-1), T(n-2), T(n-3)
results = []
# For each of [n-1, n-2, n-3], try to check if we've already found its corresponding T value
for potential_arg in [n-1, n-2, n-3]:
if potential_arg in cache: # If we've already found the T value
results.append(cache[potential_arg]) # No need to call the function again
else:
result_from_call = T_memoized(potential_arg)
results.append(result_from_call)
cache[potential_arg] = result_from_call # Save result in the cache
return sum(results) # I.e. return results[0] + results[1] + results[2]
cache = {0: 0,
1: 1,
2: 2} # Save the base cases in the cache
@decs.count_calls
def T_memoized(n):
'''Calculates T_n recursively'''
# We don't need the base cases anymore since we put them in the cache
# Check n-1
if n-1 in cache:
first = cache[n-1]
else:
first = T_memoized(n-1)
results[n-1] = first
# Check n-2
if n-2 in cache:
second = cache[n-2]
else:
second = T_memoized(n-2)
results[n-2] = second
# Check n-3
if n-3 in cache:
third = cache[n-3]
else:
third = T_memoized(n-3)
results[n-3] = third
return first + second + third
print("T_memoized(20)={}".format(T_memoized(20)))
print("{} calls were made when calculating T_memoized(20)".format(decs.get_call_count("T_memoized")))
Note that calculating T(20) required 128287 calls without memoization. But with memoization it only required 18 calls.
factor:¶factor_cache = {0: [],
1: []}
# Save the base cases in the cache (prime factorizations of 0 or 1 are empty lists)
@decs.count_calls
def factor_memoized(n):
'''Returns list of prime factors of `n`'''
# We don't need the base cases anymore since we put them in the cache
for k in range(2,n): # Check each integer from 2 to n-1
# NOTE: could reduce to 2...int(sqrt(n)) for more efficiency
if n % k == 0: # In this case, we have n = k * m for some integer m
m = int(n / k)
# Check if we've already found the prime factorization of k
if k in factor_cache:
first = factor_cache[k]
else: # Compute with recursion and save in cache
first = factor_memoized(k)
factor_cache[k] = first
# Check if we've already found the prime factorization of m
if m in factor_cache:
second = factor_cache[m]
else: # Compute with recursion and save in cache
second = factor_memoized(m)
factor_cache[m] = second
# Here, `+` is used to add two lists (i.e. append one list to the other)
return first + second
# If no factors of `n` are found, then it is prime, so it cannot be factored
factor_cache[n] = [n]
return [n]
print("The prime factors of 32768 are: {}".format(factor_memoized(32768))) # 1024 is 2^15
print("{} calls were made when calculating factors of 32768 with memoization".format(decs.get_call_count("factor_memoized")))
Without memoization, finding the prime factors of 32 768 took 29 calls. With memoization, it took 15 calls.
For large inputs, factor doesn't need to make as many calls to itself as T does. After memoization, both functions make fewer calls, but one could say that T benefits more from memoization because there is a bigger reduction in the number of calls compared to factor.