In [ ]:

```
from __future__ import division, print_function
```

We want to write a recursive function `findMinRec(l)`

to find the minimum value in list `l`

, where `l`

is a list of integers. We will break this problem into steps as shown below.

Write down the recursive case.

Write down the base case.

Now write the function `findMinRec(l)`

that finds the minimum value in the list `l`

.

For example, `findMinRec([-2,2,3]) = -2`

.

We have a list of prices for items you want to purchase. You want to calculate the total bill. Write a recursive function `findSumRec(l)`

that takes a list of integers `l`

and returns the sum of the prices in the list.

Write down the recursive case.

Write down the base case.

Write the recursive function `findSumRec(l)`

that will add all the numbers in the list to return the total sum of the bill needed to be paid.

For example, `findSumRec([55, 36, 200, 11]) = 302`

In this question we are given a string of letters where each letter represents whether a person is a spy or a commoner. So letter `"c"`

in the string represents commoner and letter `"s"`

represents spy. We want to find out how many spies are in the group. Write recursive function `countSpiesRec(s)`

where `s`

is the string of people.

Write the recursive case.

Write the base case.

Now we want to write the function `countSpiesRec(s)`

that given a string of spies and commoners, will return the number of spies (`s`

characters).

For example `countSpiesRec("scccscccccc") = 2`

.

Another example: `countSpiesRec("cccc") = 0`

.

Also: `countSpiesRec("") = 0`

.

We want to write a recursive function `multiplyRec(x, y)`

that will multiply two positive integers `x`

and `y`

together without using the multiplication operator ($*$).

Write the recursive case.

Write the base case.

Now we want to write the recursive function `multiplyRec(x, y)`

that takes in two non-negative integers and returns the product. We do not want to use the $*$ operator but rather want to do this recursively.

As you would expect, `multiplyRec(4, 5) = 20`

Also note, `multiplyRec(0, 5) = 0`

Lets write a function `findPowerTwoDivide(n)`

that takes in an integer `n`

and returns the largest power of $2$ (e.g. $2^4 = 16$) that divides `n`

evenly.

For example, `findPowerTwo(8)`

= $2^3 = 8$

For example, `findPowerTwo(9)`

= $2^0 = 1$

Lets write a function `findPowerTwoLargest(n)`

that takes in an integer `n`

and returns the largest power of $2$ (e.g. $2^4 = 16$) that less than or equal to `n`

.

For example, `findPowerTwo(8)`

= $2^3 = 8$

For example, `findPowerTwo(9)`

= $2^3 = 8$

We have a list of integers representing how much you like different people. For example you like person with score $10$ more than you like person with $-12$ or $9$. Now you are going to have a party and are trying to decide who to invite. The sum of the scores of the people you invite represents the fun you would have at the party. We want to decide which subset of people to invite in order to have the most fun party.

Write a function `bestPartyScore(friendScores)`

, where `friendScores`

is a list of integers, that returns an integer representing the fun you would have at the party.

For example, if you have `friendScores = [1, 3, 7, 11]`

, `bestPartyScore(friendScores) = 1 + 3 + 7 + 11 = 22`

.

If you have `friendScores = [1, -3, 7, 11]`

, `bestPartyScore(friendScores) = 1 + 7 + 11 = 19`

.

If you have `friendScores = [-1, -3, -7, -11]`

, `bestPartyScore(friendScores) = 0 = 0`

.

If you have `friendScores = []`

, `bestPartyScore(friendScores) = 0 = 0`

.

Now we will review the concept of binary.

Similar to how you can write numbers in decimal system (base $10$):

e.g. $1042 = 1(10^3) + 0(10^2) + 4(10^1) + 2(10^0)$

we can do this other sytems as well. Here is how we could do this in a different system. This is in base $2$ which we call the binary system:

e.g. $24 = 1(2^4) + 1(2^3) + 0(2^2) + 0(2^1) + 0(2^0)$

You can see each positive integer would have it's own unique such decomposition. As a result we can encode positive integers using just the coefficients from the above powers of $2$. So looking at $24$, if we just take the coefficients from the right hand side equation we get $11000$. This is the base $2$ encoding of $24$.

Here are some more examples:

e.g. $0 = 0(2^0) = 0$ in base $2$

e.g. $1 = 1(2^0) = 1$ in base $2$

e.g. $19 = 1(2^4) + 0(2^3) + 0(2^2) + 1(2^1) + 1(2^0) = 10011$ in base $2$

e.g. $63 = 1(2^5) + 1(2^4) + 1(2^3) + 1(2^2) + 1(2^1) + 1(2^0) = 111111$ in base $2$

e.g. $685 = 1(2^9) + 0(2^8) + 1(2^7) + 0(2^6) + 1(2^5) + 0(2^4) + 1(2^3) + 1(2^2) + 0(2^1) + 1(2^0) = 101010110$ in base $2$

Try to do the equivalent for $39$. Write the corresponding binary encoding.

We want to write a recursive function `decimalToBinary(x)`

that takes in a positive integer `x`

and returns a string that represents the binary form of `x`

.

e.g. `decimalToBinary(0) = "0"`

e.g. `decimalToBinary(19) = "10011"`

Jack the frog wants to hop home from a restaurant. He has to cross the river from the restaurant at rock `n`

to his home at rock $0$. The rocks have equal distance of $1$ between them and he can jump over any number of rocks in the direction of his house and does not go backwards. In how many different ways can he reach home? Two ways are different if they do not use exactly the same rock route. Write a recursive function `gettingHome(n)`

that takes in integer `n`

representing the distance between the restaurant and home, and returns the number of ways for Jack to return home.

For example, when `n = 3`

, `gettingHome(n) = 4`