*Due by 11:59 PM on (that is, the end of) Friday, 6/29*

**This homework must be submitted online.** We do not
require a paper copy.

**To turn in the electronic copy**, submit all of your
answers in a file named `hw3.py`. Follow the instructions here to submit the electronic copy.

**Readings.** All problems in this homework can be solved
with the subset of Python 3 introduced in sections 1.1-1.7 of the lecture
notes.

If you would like, you can use the template file `hw3.py`

.
To copy this file to your lab account you can run the command:

cp ~cs61a/lib/hw/hw03/hw3.py .

to copy it into your current directory.

**Q0.** We would like to know if you are going to have any
conflicts with the exam dates and times. Check your schedule (like the
schedules for other classes you might have) to see if you have any conflicts and
fill out this
form (even if you have emailed us already).

**Q1.** A mathematical function `g` is defined by two cases:

g(n) = n, if n <= 3 g(n) = g(n - 1) + 2 * g(n - 2) + 3 * g(n - 3), if n > 3

Write a recursive function that computes `g`. Then, write an iterative function, `g_iter`, that computes the same values.

**Q2.** Rewrite the continued fraction function from the
last homework (question 4), `continued_frac`, to
use recursion instead of iteration (so do **not** use a while
loop). *Hint:* try writing a recursive helper function to do most of the
work, rather than trying to do the recursion with `continued_frac` directly.

def continued_frac(n_term, d_term, k): """Returns the k-term continued fraction with numerators defined by n_term and denominators defined by d_term. >>> # golden ratio ... round(continued_frac(lambda x: 1, lambda x: 1, 8), 3) 0.618 >>> # 1 / (1 + (2 / (2 + (3 / (3 + (4 / 4)))))) ... round(continued_frac(lambda x: x, lambda x: x, 4), 6) 0.578947 """

**Q3.** A classic puzzle called the Towers of Hanoi is a
game that consists of three rods, and a number of disks of different sizes which
can slide onto any rod. The puzzle starts with the disks in a neat stack in
ascending order of size on one rod, the smallest at the top, thus making a
conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

- Only one disk may be moved at a time.
- Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
- No disk may be placed on top of a smaller disk.

Complete the definition of `tower_of_hanoi` which prints out the steps to solve this puzzle for
any number of `n` disks starting from the `start` rod and moving them to the `end` rod.

def tower_of_hanoi(n, start, end): """Print the moves required to solve the tower of hanoi game if we start with n disks on the start pole and want to move them all to the end pole. The game is to assumed to have 3 poles (which is traditional). >>> tower_of_hanoi(1, 1, 3) Move 1 disk from rod 1 to rod 3 >>> tower_of_hanoi(2, 1, 3) Move 1 disk from rod 1 to rod 2 Move 1 disk from rod 1 to rod 3 Move 1 disk from rod 2 to rod 3 >>> tower_of_hanoi(3, 1, 3) Move 1 disk from rod 1 to rod 3 Move 1 disk from rod 1 to rod 2 Move 1 disk from rod 3 to rod 2 Move 1 disk from rod 1 to rod 3 Move 1 disk from rod 2 to rod 1 Move 1 disk from rod 2 to rod 3 Move 1 disk from rod 1 to rod 3 """

**Q4.** The number of *partitions* of a positive
integer is the number of ways in which it can be expressed as the sum of
positive integers in increasing order. For example, the number 5 has 7
partitions:

5 = 5 5 = 1 + 4 5 = 2 + 3 5 = 1 + 1 + 3 5 = 1 + 2 + 2 5 = 1 + 1 + 1 + 2 5 = 1 + 1 + 1 + 1 + 1

To find the number of partitions for a given number, one can solve an
easier problem of finding all of the partitions of a number `n` only using integers greater than or equal to another integer `k`. Solve this easier problem by writing a
tree-recursive function `part_help(n, k)` that
returns the number of partitions of `n` using
integers greater than or equal to k.

def part_help(m, k): """Return the number of partitions of m that use integers greater than or equal to k. >>> part_help(3, 2) # 3 1 >>> part_help(3, 1) # 3, 2 + 1, 1 + 1 + 1 3 """ "*** YOUR CODE HERE ***" def part(n): """Return the number of partitions of positive integer n. >>> part(5) 7 >>> part(7) 15 """ return part_help(n, 1)

**Extra for Experts:**

*Note*: "Extra for Experts" problems are completely
optional. You are encouraged to try these questions. However, these are
questions which we consider more difficult than what we would consider asking
you on an exam, so please don't be discouraged if you don't solve them.

**Q5.** The recursive factorial function can be written as
a single expression by using a conditional expression.:

>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1))) >>> fact(5) 120

To write a recursive function previously, we have always given it a
name using a `def` or assignment statement so
that we can refer to the function within its own body. In this question, your
job is to define fact without giving it a name (although we give a name to allow for
doctests)!

Write an expression that computes `n`
factorial using only call expressions, conditional expressions, and lambda
expressions (no assignment or def statements).

*Hint:* Googling Y-combinator will tell you the solution, so
don't do that until you've tried to solve the problem yourself!