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

# MCS 275 Spring 2022 Worksheet 6¶

• Course instructor: David Dumas

## Topics¶

The main topics of this worksheet is recursion.

The other worksheet from this course that focuses on recursion is here.

## Resources¶

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.

## 1. Order three Fibonacci¶

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

## 2. Prime factorization¶

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.

## 3. Parentheses¶

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)))
• and more

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.

In [2]:
put_parens([2,1,5,8]) # find all ways to put parentheses in the expression 2+1+5+8

Out[2]:
[[2, [1, [5, 8]]],
[2, [[1, 5], 8]],
[[2, 1], [5, 8]],
[[2, [1, 5]], 8],
[[[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)

## 4. Rote memoization¶

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?