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$.
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.
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.
put_parens([2,1,5,8]) # find all ways to put parentheses in the expression 2+1+5+8
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)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?