# Lab 6: Recursion and Midterm Review

*Due at 11:59:59 pm on 10/22/2019.*

## Starter Files

Download lab06.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

## Submission

By the end of this lab, you should have submitted the lab with `python3 ok --submit`

. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

When you are ready to submit, run `ok`

with the `--submit`

option:

`python3 ok --submit`

After submitting, `ok`

will display a submission URL, with which you can view your submission on okpy.org.

## Recursion

A recursive function is a function that calls itself in its body, either directly or indirectly. Recursive functions have three important components:

- Base case(s), the simplest possible form of the problem you're trying to solve.
- Consider a recursive call on a smaller argument.
- Recursive case(s), where the function calls itself with a
*simpler argument*as part of the computation.

Let's look at the canonical example, `factorial`

:

```
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
```

We know by its definition that `0!`

is `1`

. So we choose `n = 0`

as our
base case. The recursive step also follows from the definition of
factorial, i.e. `n! = n * (n-1)!`

.

The next few questions in lab will have you writing recursive functions. Here are some general tips:

- Consider how you can solve the current problem using the solution to
a simpler version of the problem. Remember to
*trust the recursion*: assume that your solution to the simpler problem works correctly without worrying about how. - Think about what the answer would be in the simplest possible case(s). These will be your base cases - the stopping points for your recursive calls. Make sure to consider the possibility that you're missing base cases (this is a common way recursive solutions fail).
- It may help to write the iterative version first.

## Required Questions

### Question 1: A Bad List Flattener

There is something wrong with the following code! Figure out what is wrong with it, and then fix it to pass the doc string.

Hint, your fix should be very minor! Do not rewrite the whole program.

```
def bad_list_flattener(lst1, lst2):
"""
Flattens both lst1 and lst2, and returns the
concatenation of the two flattened lists. Flattening
a list means to collapse the list into one
dimension (like np.flatten).
>>> girls = [['Rachel', 'Green'], ['Phoebe', 'Buffay']]
>>> boys = [['Ross', 'Geller'], ['Chandler', 'Bing']]
>>> bad_list_flattener(girls, boys)
['Rachel', 'Green', 'Phoebe', 'Buffay', 'Ross', 'Geller', 'Chandler', 'Bing']
>>> cats = [['Persian'], ['British', 'Shorthair']]
>>> dogs = [['Golden', 'Retriever']]
>>> bad_list_flattener(dogs, cats)
['Golden', 'Retriever', 'Persian', 'British', 'Shorthair']
"""
newlist1 = []
newlist2 = []
for inner_lst in lst1:
for item in inner_lst:
newlist1 += item
for inner_lst in lst2:
for item in inner_lst:
newlist2 += item
return newlist1 + newlist2
```

```
def bad_list_flattener(lst1, lst2):
"""
Flattens both lst1 and lst2, and returns the
concatenation of the two flattened lists. Flattening
a list means to collapse the list into one
dimension (like np.flatten).
>>> girls = [['Rachel', 'Green'], ['Phoebe', 'Buffay']]
>>> boys = [['Ross', 'Geller'], ['Chandler', 'Bing']]
>>> bad_list_flattener(girls, boys)
['Rachel', 'Green', 'Phoebe', 'Buffay', 'Ross', 'Geller', 'Chandler', 'Bing']
>>> cats = [['Persian'], ['British', 'Shorthair']]
>>> dogs = [['Golden', 'Retriever']]
>>> bad_list_flattener(dogs, cats)
['Golden', 'Retriever', 'Persian', 'British', 'Shorthair']
"""
newlist1 = []
newlist2 = []
for inner_lst in lst1:
for item in inner_lst:
newlist1 += item
for inner_lst in lst2:
for item in inner_lst:
newlist2 += item
return newlist1 + newlist2
```

Use OK to test your code:

`python3 ok -q bad_list_flattener`

### Question 2: is_palindrome

Write a recursive solution for the function `is_palindrome`

such that it takes in any list and returns True if that list is the same way going forwards and backwards.

```
def is_palindrome(lst):
""" Returns True if the list is a palindrome. A palindrome is a list
that reads the same forwards as backwards
>>> is_palindrome([1, 2, 3, 4, 5])
False
>>> is_palindrome(["p", "a", "l", "i", "n", "d", "r", "o", "m", "e"])
False
>>> is_palindrome([True, False, True])
True
>>> is_palindrome([])
True
>>> is_palindrome(["a", "v", "a"])
True
>>> is_palindrome(["racecar", "racecar"])
True
>>> is_palindrome(["r", "a", "c", "e", "c", "a", "r"])
True
"""
"*** YOUR CODE HERE ***"
if len(lst) == 0 or len(lst) == 1:
return True
if lst[0] != lst[-1]:
return False
return is_palindrome(lst[1:-1])
```

Use OK to test your code:

`python3 ok -q is_palindrome`

### Question 3: AB Plus C

Implement `ab_plus_c`

, a function that takes arguments `a`

, `b`

, and
`c`

and computes `a * b + c`

. You can assume a and b are both nonnegative
integers. However, you can't use the `*`

operator. Try recursion!

```
def ab_plus_c(a, b, c):
"""Computes a * b + c.
>>> ab_plus_c(2, 4, 3) # 2 * 4 + 3
11
>>> ab_plus_c(0, 3, 2) # 0 * 3 + 2
2
>>> ab_plus_c(3, 0, 2) # 3 * 0 + 2
2
"""
"*** YOUR CODE HERE ***"
if b == 0:
return c
return a + ab_plus_c(a, b - 1, c)
```

Use OK to test your code:

`python3 ok -q ab_plus_c`

### Question 4: GCD

The greatest common divisor of two positive integers `a`

and `b`

is the
largest integer which evenly divides both numbers (with no remainder).
Euclid, a Greek mathematician in 300 B.C., realized that the greatest
common divisor of `a`

and `b`

is one of the following:

- the smaller value if it evenly divides the larger value, OR
- the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value

In other words, if `a`

is greater than `b`

and `a`

is not divisible by
`b`

, then

`gcd(a, b) == gcd(b, a % b)`

Write the `gcd`

function recursively using Euclid's algorithm.

```
def gcd(a, b):
"""Returns the greatest common divisor of a and b.
Should be implemented using recursion.
>>> gcd(34, 19)
1
>>> gcd(39, 91)
13
>>> gcd(20, 30)
10
>>> gcd(40, 40)
40
"""
"*** YOUR CODE HERE ***"
a, b = max(a, b), min(a, b)
if a % b == 0:
return b
else:
return gcd(b, a % b)
```

Use OK to test your code:

`python3 ok -q gcd`

This is an example of the elegance that recursive solutions permit. Here for comparison is an iterative solution.

```
# Iterative solution, if you're curious
def gcd_iter(a, b):
"""Returns the greatest common divisor of a and b, using iteration.
>>> gcd_iter(34, 19)
1
>>> gcd_iter(39, 91)
13
>>> gcd_iter(20, 30)
10
>>> gcd_iter(40, 40)
40
"""
if a < b:
a, b = b, a
while a > b and not a % b == 0:
a, b = b, a % b
return b
```

### Question 5: Adding matrices

To practice, write a function that adds two matrices together using list comprehensions. The function should take in two 2D lists of the same dimensions. Try to implement this in one line!

```
def add_matrices(x, y):
"""
>>> matrix1 = [[1, 3],
... [2, 0]]
>>> matrix2 = [[-3, 0],
... [1, 2]]
>>> add_matrices(matrix1, matrix2)
[[-2, 3], [3, 2]]
"""
"*** YOUR CODE HERE ***"
return [[x[i][j] + y[i][j] for j in range(len(x[0]))]
for i in range(len(x))]
```

Use OK to test your code:

`python3 ok -q add_matrices`

### Question 6: Mul_by_num

Using higher order functions, complete the `mul_by_num`

function. This
function should take an argument and return a one argument function
that multiplies any value passed to it by the original number.

```
def mul_by_num(num):
"""
Returns a function that takes one argument and returns num
times that argument.
>>> x = mul_by_num(5)
>>> y = mul_by_num(2)
>>> x(3)
15
>>> y(-4)
-8
"""
"*** YOUR CODE HERE ***"
def f(x):
return num*x
return f
```

Use OK to test your code:

`python3 ok -q mul_by_num`

### Question 7: Skip Add

Write a function `skip_add`

that takes a single argument `n`

and computes the sum of every other integer between 0 and `n`

starting from n. Assume `n`

is non-negative.

```
def skip_add(n):
""" Takes a number x and returns x + x-2 + x-4 + x-6 + ... + 0.
>>> skip_add(5) # 5 + 3 + 1 + 0
9
>>> skip_add(10) # 10 + 8 + 6 + 4 + 2 + 0
30
"""
"*** YOUR CODE HERE ***"
if n <= 0:
return 0
return n + skip_add(n - 2)
```

Use OK to test your code:

`python3 ok -q skip_add`

## Extra Questions

Extra questions are not worth extra credit and are entirely optional. They are designed to challenge you to think creatively!

### Question 8: Towers of Hanoi

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"
"*** YOUR CODE HERE ***"
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)
```

Use OK to test your code:

`python3 ok -q move_stack`