Due by 9:00pm on Friday, 10/05/2018

## Instructions

Download hw05.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 the homework by uploading the `hw05.py` file to okpy.org. You may submit more than once before the deadline; only the final submission will be scored.

Readings: This homework relies on following references:

## Recursion: revisiting Map, Filter, and Reduce

In this next section you are going to implement the filter and reduce functions we learned in lab04 using recursion. Feel free to refer to lab04 for guidance and more examples Lab04.

We wrote the recursive version of the function `map` in lecture. Here it is again:

`map` takes

• m - a one-argument function that you want to map onto each element in the list.
• s - a sequence of values
``````def map(f, s):
"""
Map a function f onto a sequence.

>>> def double(x):
...     return x * 2
>>> def square(x):
...     return x ** 2
>>> def toLetter(x):
...     alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
...     return alpha[x%26]
>>> map(double, [1,2,3,4])
[2, 4, 6, 8]
>>> map(square, [1, 2, 3, 4, 5, 10])
[1, 4, 9, 16, 25, 100]
>>> map(toLetter, [3, 0, 19, 0])
['d', 'a', 't', 'a']

"""
if s == []:
return s
return [f(s[0])] + map(f, s[1:])``````

### Question 1: Filter

Write the recursive version of the function `filter` which takes

• filter - a one-argument function that returns True if the argument passed in should be included in the list, and False otherwise.
• s - a sequence of values
``````def filter(f, s):
"""Filter a sequence to only contain values allowed by filter.

>>> def is_even(x):
...     return x % 2 == 0
>>> def divisible_by5(x):
...     return x % 5 == 0
>>> filter(is_even, [1,2,3,4])
[2, 4]
>>> filter(divisible_by5, [1, 4, 9, 16, 25, 100])
[25, 100]
"""
return _____``````

Use OK to test your code:

``python3 ok -q filter --local``

### Question 2: 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, s, base):
"""Reduce a sequence under a two-argument function starting from a base value.

...     return x + y
>>> def mul(x, y):
...     return x*y
10
>>> reduce(mul, [1,2,3,4], 0)
0
>>> reduce(mul, [1,2,3,4], 1)
24
"""
return _____``````

Use OK to test your code:

``python3 ok -q reduce --local``

## Recursion: Let's do some Math

### Question 3: Number representation

Whenever we think of numbers, we are actually thinking of them in relation to some base. Typically that base is 10. Each number can be decomposed as a combination of the powers of it's base.

`134 = 1 * 10^2 + 3 * 10^1 + 4 * 10^0`

Write a function that takes a number and returns a list of it's decimal representation.

``````def decimal(n):
"""Return a list representing the decimal representation of a number.

>>> decimal(55055)
[5, 5, 0, 5, 5]
>>> decimal(-136)
['-', 1, 3, 6]
"""

Use OK to test your code:

``python3 ok -q decimal --local``

We can also represent numbers in different bases. Think of how you could represent the number 5 in base 2. Essentially, how can you break the number 5 into powers of 2. It contains one 4 and one 1. In base 2, your digit overflows after 1, so this representation of numbers only has 1 and 0.

`5 = 1 * 2^2 + 0 * 2^1 + 1 * 2^0`

Write a function that takes a number and returns a list of it's representation in base 2.

``````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]
"""

Use OK to test your code:

``python3 ok -q binary --local``

### Question 4: Count Digit

Write a function that takes a positive integer `n` and returns the number of times the number `digit` appears. Do not use any assignment statements.

``````def count_digit(n, digit):
"""Return how many times digit appears in n.

>>> count_digit(55055, 5)
4
>>> count_digit(1231421, 1)
3
>>> count_digit(12, 3)
0
"""

Use OK to test your code:

``python3 ok -q count_digit --local``

### Question 5: Ten-Pairs

Write a function that takes a positive integer `n` and returns the number of ten-pairs it contains. A ten-pair is a pairs of digits within `n` that sum to 10. Do not use any assignment statements.

The number 7,823,952 has 3 ten-pairs. The first and fourth digits sum to 7+3=10, the second and third digits sum to 8+2=10, and the second and last digit sum to 8+2=10:

Hint: What if you had a function that counted the times a certain digit appeared.

``````def ten_pairs(n):
"""Return the number of ten-pairs within positive integer n.

>>> ten_pairs(7823952)
3
>>> ten_pairs(55055)
6
>>> ten_pairs(9641469)
6
"""

Use OK to test your code:

``python3 ok -q ten_pairs --local``

## Challenge Questions

Questions in this section are not required for submission.

### Question 6: Count Change

A set of coins makes change for `n` if the sum of the values of the coins is `n`. For example, if you have 1-cent, 2-cent and 4-cent coins, the following sets make change for `7`:

• 7 1-cent coins
• 5 1-cent, 1 2-cent coins
• 3 1-cent, 2 2-cent coins
• 3 1-cent, 1 4-cent coins
• 1 1-cent, 3 2-cent coins
• 1 1-cent, 1 2-cent, 1 4-cent coins

Thus, there are 6 ways to make change for `7`. Write a function `count_change` that takes a positive integer `n` and a list of the coin denominations and returns the number of ways to make change for `n` using these coins (Hint: You will need to use tree recursion):

``````def count_change(amount, denominations):
"""Returns the number of ways to make change for amount.

>>> denominations = [50, 25, 10, 5, 1]
>>> count_change(7, denominations)
2
>>> count_change(100, denominations)
292
>>> denominations = [16, 8, 4, 2, 1]
>>> count_change(7, denominations)
6
>>> count_change(10, denominations)
14
>>> count_change(20, denominations)
60
"""

Use OK to test your code:

``python3 ok -q count_change --local``

### Question 7: Fibonacci Tail

Write a tail recursive function that returns the `nth` element of the fibonacci sequence.

As a reminder, Fibonacci is defined as a function where:

For Example: `def f(a = 1):` defines a function named f that requires an argument `a`. If `a` is not specified `a` gets the value `1`. `f()` is the same as typing `f(1)` in this case.

``````def fibonacci(n, nMinus2 = 0, nMinus1 = 1):
"""Return the nth fibonacci number.

>>> fibonacci(11)
89
>>> fibonacci(5)
5
>>> fibonacci(0)
0
>>> fibonacci(1)
1
"""
``python3 ok -q fibonacci --local``