# CS 61A

Time: Tue 9/26/17 2 pm

## Recursions

### Verbose Factorial

Here's a good way to visualize factorials--but a little challenging to code. Write a functional `verbose_fact(n)` that prints out the steps to reduce the recursive cases to a base case. You may utilize the params `fact_so_far` and `prefix` to help with building up your solution.

``````def verbose_fact(n, fact_so_far = 1, prefix = ""):
"""
>>> verbose_fact(1)
1!
= 1
>>> verbose_fact(2)
2!
= 2 x 1!
= 2 x 1
= 2
>>> verbose_fact(3)
3!
= 3 x 2!
= 3 x 2 x 1!
= 3 x 2 x 1
= 6
"""

assert n >= 1, "Use n >= 1"

Solution
``````def verbose_fact(n, fact_so_far = 1, prefix = ""):
"""
>>> verbose_fact(1)
1!
= 1
>>> verbose_fact(2)
2!
= 2 x 1!
= 2 x 1
= 2
>>> verbose_fact(3)
3!
= 3 x 2!
= 3 x 2 x 1!
= 3 x 2 x 1
= 6
"""

assert n >= 1, "Use n >= 1"

# Check if it's the first time calling the function
if not prefix:
# First time
print("  " + str(n) + "!")
else:
# Not the first time
print("= " + prefix + str(n) + "!")

# Check if recursion is finished
if n == 1:
# Base case, end of recursion
if prefix: print("= " + prefix + str(n)) # Print the simplified "1!"
# Print out the solution
print("= " + str(fact_so_far * n))
else:
# Continue by recursion
verbose_fact(n - 1, fact_so_far * n, prefix + str(n) + " x ")``````

### Towers of Hanoi (fa16-hw5-3)

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 n disks in a neat stack in ascending order of size on a `start` rod, the smallest at the top, forming a conical shape.

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

• Only one disk may be moved at a time.
• Each move consists of taking the top (smallest) 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 `move_stack`, which prints out the steps required to move `n` disks from the `start` rod to the `end` rod without violating the rules.

``````def print_move(origin, destination):
"""
Print instructions to move a disk.
"""

print("Move the top disk from rod", origin, "to rod", destination)

def move_stack(n, start, end):
"""
Print the moves required to move n disks on the start pole to the end pole without violating the rules of Towers of Hanoi.

n -- number of disks
start -- a pole position, either 1, 2, or 3
end -- a pole position, either 1, 2, or 3

There are exactly three poles, and start and end must be different. Assume
that the start pole has at least n disks of increasing size, and the end
pole is either empty or has a top disk larger than the top n start disks.

>>> move_stack(1, 1, 3)
Move the top disk from rod 1 to rod 3
>>> move_stack(2, 1, 3)
Move the top disk from rod 1 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 3
>>> move_stack(3, 1, 3)
Move the top disk from rod 1 to rod 3
Move the top disk from rod 1 to rod 2
Move the top disk from rod 3 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 1
Move the top disk from rod 2 to rod 3
Move the top disk from rod 1 to rod 3
"""

assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"

Solution
``````def print_move(origin, destination):
"""
Print instructions to move a disk.
"""

print("Move the top disk from rod", origin, "to rod", destination)

def move_stack(n, start, end):
"""
Print the moves required to move n disks on the start pole to the end pole without violating the rules of Towers of Hanoi.

n -- number of disks
start -- a pole position, either 1, 2, or 3
end -- a pole position, either 1, 2, or 3

There are exactly three poles, and start and end must be different. Assume
that the start pole has at least n disks of increasing size, and the end
pole is either empty or has a top disk larger than the top n start disks.

>>> move_stack(1, 1, 3)
Move the top disk from rod 1 to rod 3
>>> move_stack(2, 1, 3)
Move the top disk from rod 1 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 3
>>> move_stack(3, 1, 3)
Move the top disk from rod 1 to rod 3
Move the top disk from rod 1 to rod 2
Move the top disk from rod 3 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 1
Move the top disk from rod 2 to rod 3
Move the top disk from rod 1 to rod 3
"""

assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
if n == 1:
print_move(start, end)
else:
other = 6 - start - end
move_stack(n - 1, start, other)
print_move(start, end)
move_stack(n - 1, other, end)``````

They are naturally sustainable! Oh well, think about how trees are conceptually related to pairs. Define the terminologies around trees--root, node, leaf node (the language we use may vary in different places).

Consider the following implementation:

``````def tree(label, branches=[]):
return [label] + branches

def label(tree):
return tree

def branches(tree):
return tree[1:]``````

There are multiple ways to get started on playing with such tree structure! As a few examples:

1. Given a tree, how can we find a largest/smallest label in the leaves?
2. Given a tree, how can we find a largest/smallest label in the tree?
3. Given a tree, how can we find the sum of all labels (assuming all labels are numbers)?
4. Given a tree, how can we make a copy of it with all the leaves pruned? The function is non-destructive.
5. Given a tree and a label, how can we check if the label we want is in the tree?
6. Given a tree, how can we check if there aren't any descendent nodes of a same label for any node in the tree?

And here's sample tree to work with:

``````sample_tree = \       # the back slash is here to break the line
tree(5, [
tree(-5),
tree(10, [
tree(2),
tree(5, [
tree(3, [
tree(15, [
tree(-2)  # Leaf
])
]),
tree(4),      # Leaf
tree(5, [
tree(99),   # Leaf
tree(6)
])
])
])
])``````