#
Homework 6

*Due at 11:59:59 pm on Sunday, 10/17/2021.*

## Instructions

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

**Submission:** When you are done, submit with `python3 ok --submit`

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

**Readings:** This homework relies on following references:

## Recursion

### Question 1: Reduce

Write the recursive version of the function `reduce`

which takes

- reducer - a two-argument function that reduces elements to a single value
- s - a sequence of values
- base - the starting value in the reduction. This is usually the identity of the reducer

If you're feeling stuck, think about the parameters of `reduce`

.

```
from operator import add, mul
def reduce(reducer, seq, base):
"""Reduce a sequence under a two-argument function starting from a base value.
>>> def add(x, y):
... return x + y
>>> def mul(x, y):
... return x*y
>>> reduce(add, [1,2,3,4], 0)
10
>>> reduce(mul, [1,2,3,4], 0)
0
>>> reduce(mul, [1,2,3,4], 1)
24
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q reduce`

### Question 2: Remove Last from Sequence

Complete the recursive function `remove_last`

which creates a new list identical to the input list `s`

but with the last element in the sequence that is equal to `x`

removed.

```
def remove_last(x, s):
"""Create a new list that is identical to s but with the last
element from the list that is equal to x removed.
>>> remove_last(1,[])
[]
>>> remove_last(1,[1])
[]
>>> remove_last(1,[1,1])
[1]
>>> remove_last(1,[2,1])
[2]
>>> remove_last(1,[3,1,2])
[3, 2]
>>> remove_last(1,[3,1,2,1])
[3, 1, 2]
>>> remove_last(5, [3, 5, 2, 5, 11])
[3, 5, 2, 11]
"""
"*** YOUR CODE HERE ***"
```

Illustrated here is a more complete doctest that shows good testing methodology. It is a little cumbersome as documentation, but you'll want to think about it for your projects. Test every condition that might come up. Then you won't be surprised when it does.

Use OK to test your code:

`python3 ok -q remove_last`

### Question 3: Binary

Write the recursive version of the function `binary`

which takes in `n`

, a number, and returns a list representing the representation of the number in base 2.

You may find the following article helpful in understanding how to convert a number from decimal to binary.

```
def binary(n):
"""Return a list representing the representation of a number in base 2.
>>> binary(55055)
[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
>>> binary(-136)
['-', 1, 0, 0, 0, 1, 0, 0, 0]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q binary`

### Question 4: Hailstone

For the `hailstone`

function from previously, you pick a positive
integer `n`

as the start. If `n`

is even, divide it by 2. If `n`

is
odd, multiply it by 3 and add 1. Repeat this process until `n`

is 1.
Write a recursive version of hailstone that prints out the values of
the sequence and returns the number of steps.

```
def hailstone_iterative(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
>>> a = hailstone_iterative(10)
10
5
16
8
4
2
1
>>> a
7
"""
"*** YOUR CODE HERE ***"
def hailstone_recursive(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
>>> a = hailstone_recursive(10)
10
5
16
8
4
2
1
>>> a
7
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

```
python3 ok -q hailstone_iterative
python3 ok -q hailstone_recursive
```

### Question 5: 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", "l", "a", "s", "k", "a"])
False
>>> is_palindrome(["r", "a", "d", "a", "r"])
True
>>> is_palindrome(["f", "o", "o", "l", "p", "r", "o", "o", "f"])
False
>>> is_palindrome(["a", "v", "a"])
True
>>> is_palindrome(["racecar", "racecar"])
True
>>> is_palindrome(["r", "a", "c", "e", "c", "a", "r"])
True
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q is_palindrome`

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`