# Homework 5 Solutions

**Solutions:** You can find the file with solutions for all
questions here.

## 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]
"""
if s == []:
return s
if f(s[0]):
return [s[0]] + filter(f, s[1:])
return filter(f, s[1:])
```

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.
>>> 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
"""
if s == []:
return base
next_base = reducer(base, s[0])
return reduce(reducer, s[1:], next_base)
```

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]
"""
if n < 0:
return ['-'] + decimal(-1 * n)
elif n < 10:
return [n % 10]
else:
return decimal(n // 10) + [n % 10]
```

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]
"""
if n < 0:
return ['-'] + binary(-1 * n)
elif n < 2:
return [n % 2]
else:
return binary(n // 2) + [n % 2]
```

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
"""
if n == 0:
return 0
if n%10 == digit:
return count_digit(n//10, digit) + 1
else:
return count_digit(n//10, digit)
```

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
"""
if n < 10:
return 0
else:
return ten_pairs(n//10) + count_digit(n//10, 10 - n%10)
def count_digit(n, digit):
"""Return how many times digit appears in n.
>>> count_digit(55055, 5)
4
"""
if n == 0:
return 0
else:
if n%10 == digit:
return count_digit(n//10, digit) + 1
else:
return count_digit(n//10, digit)
```

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
"""
if amount < 0 or denominations == []:
return 0
elif amount == 0:
return 1
using_coin = count_change(amount - denominations[0], denominations)
not_using_coin = count_change(amount, denominations[1:])
return using_coin + not_using_coin
```

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:

In your function signature, you can add default values for arguments.

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
"""
if n == 0:
return n
if n == 1:
return nMinus1
return fibonacci(n - 1, nMinus1 , nMinus1 + nMinus2)
```

Use OK to test your code:

`python3 ok -q fibonacci --local`