#!/usr/bin/env python
# coding: utf-8

# # Lecture 4, Part 2 Exercises (2018 revision)
# 
# ## *All of your answers should use recursion!*
# ## *No loops allowed!!*

# ## Question 0: Warm-Up
# Look at this recursive function `repeatPrint()`. Notice how there are no loops!

# In[1]:


def repeatPrint(text, howManyTimes):
    if howManyTimes == 0:
        return
    else:
        print(text)
        repeatPrint(text, howManyTimes - 1)

repeatPrint('Hello AddisCoder', 3)
repeatPrint('Recursion is the best', 8)


# #### 0.1
# What is the recursive case for `repeatPrint()`? Please use English.

# In[2]:


# YOUR ANSWER HERE


# #### 0.2 
# What is the base case for `repeatPrint()`? Please use English. 

# In[3]:


# YOUR ANSWER HERE


# ## Question 1    
# 
# Consider a recursive function called `sumAll(lst)`. 
# * It takes a list of numbers, `lst`, as input.
# * It returns the sum of the list.
# 
# For example:
# 
# ```
# sumAll([1, 1, 1]) == 3
# sumAll([1, 2, 3]) == 6
# sumAll([]) == 0
# sumAll([1, -1]) == 0
# ```
# 
# #### 1.1
# What is the recursive case for `sumAll()`? Describe your answer using English.

# In[4]:


# YOUR ANSWER HERE


# #### 1.2
# What is the base case for `sumAll()`? Use English.

# In[5]:


# YOUR ANSWER HERE


# #### 1.3
# Use your base case and recursive case to write a `sumAll()` function

# In[6]:


def sumAll(lst):
    # YOUR ANSWER HERE
    return

# After you finish, these should all print True
print(sumAll([1, 1, 1]) == 3)
print(sumAll([1, 2, 3]) == 6)
print(sumAll([]) == 0)
print(sumAll([1, -1]) == 0)


# ## Question 2
# Consider a recursive function called `numTimes(s, letter)`:
# * It takes a string `s` and a single letter `letter`.
# * It returns how many times `letter` appears in `s`.
# 
# For example:
# 
# ```
# numTimes('aaabbaaab', 'b') == 3
# numTimes('aaabbaaab', 'a') == 6
# numTimes('c', 'c') == 1
# numTimes('abcd', 'e') == 0
# numTimes('', 'a') == 0
# ```
# 
# #### 2.1
# What is the recursive case for `numTimes()`? 

# In[7]:


# YOUR ANSWER HERE


# #### 2.2
# What is the base case for `numTimes()`?

# In[8]:


# YOUR ANSWER HERE


# #### 2.3
# Write a `numTimes()` function using your base and recursive cases. 

# In[9]:


def numTimes(s, letter):
    # YOUR CODE HERE
    return

# After you finish, these should all print True
print(numTimes('aaabbaaab', 'b') == 3)
print(numTimes('aaabbaaab', 'a') == 6)
print(numTimes('c', 'c') == 1)
print(numTimes('abcd', 'e') == 0)
print(numTimes('', 'a') == 0)


# ## Question 3
# Use recursion to write an exponential function, `exp(a, b)`, that calculates $a^b$. 
# 
# Some examples: 
# 
# ```
# exp(5, 2)   == 25
# exp(5, 3)   == 125
# exp(2, 3)   == 8
# exp(1, 100) == 1
# exp(5, 0)   == 1
# exp(123, 0) == 1
# ```
# 
# Assume: 
# 
# * $a$ and $b$ are integers.
# * $a >= 1$
# * $b >= 0$
# 
# Under these assumptions, we know two things about $a^b$:
# 1. $a^0 = 1$
# 2. $a^b = a \cdot a^{b-1}$

# #### 3.1
# Looking at the math above, what is the recursive case for `exp(a, b)`?

# In[10]:


# YOUR ANSWER HERE


# #### 3.2
# What is the base case for `exp(a, b)`?

# In[11]:


# YOUR ANSWER HERE


# #### 3.3 
# Write code for `exp(a, b)`

# In[12]:


def exp(a, b):
    # YOUR CODE HERE
    return

# After you finish, these should all print True
print(exp(5, 2)   == 25)
print(exp(5, 3)   == 125)
print(exp(2, 3)   == 8)
print(exp(1, 100) == 1)
print(exp(5, 0)   == 1)
print(exp(171, 0) == 1)


# ## Question 4
# Make a recursive function called `reverse(s)` that takes a string, `s`, and reverses it.
# 
# For example: 
# 
# ```
# reverse('abc') == 'cba'
# reverse('ccc') == 'ccc'
# reverse('this is a long string') == 'gnirts gnol a si siht'
# reverse('') == ''
# ```

# #### 4.1
# What is the recursive case for `reverse(s)`? 

# In[13]:


# YOUR ANSWER HERE


# #### 4.2 
# What is the base case for `reverse(s)`?

# In[14]:


# YOUR ANSWER HERE


# #### 4.3
# Write code for `reverse(s)`

# In[15]:


def reverse(s):
    # YOUR CODE HERE
    return
    
# After you finish, these should all print True
print(reverse('abc') == 'cba')
print(reverse('ccc') == 'ccc')
print(reverse('this is a long string') == 'gnirts gnol a si siht')
print(reverse('') == '')


# ## Question 5
# Define a recursive function `removeLetter(s, letter)` which: 
# * Takes a string `s` and a single character `letter`.
# * Returns the string back without the given letter.

# In[16]:


def removeLetter(s, letter):
    # YOUR CODE HERE
    return

# After you finish, these should all print True
print(removeLetter('abc', 'a') == 'bc')
print(removeLetter('abaca', 'a') == 'bc')
print(removeLetter('abc', 'd') == 'abc')
print(removeLetter('', 'a') == '')
print(removeLetter('letter', 't') == 'leer')


# ## Question 6
# 
# Define a recursive function called `sumDigits(n)` which:
# 1. Takes an int `n` as an argument. Assume `n >= 0`. 
# 2. Returns the sum of the digits of `n`. For example: 
# ```
# sumDigits(111) == 3   # because 1 + 1 + 1 == 3
# sumDigits(123) == 5   # because 1 + 2 + 3 == 5
# sumDigits(505) == 10  # because 5 + 0 + 5 == 10
# ```
# Hint: use the `%` and `//` operators

# In[17]:


def sumDigits(n):
    # YOUR CODE HERE
    return

# After you finish, these should all print True
print(sumDigits(111) == 3)
print(sumDigits(123) == 3)
print(sumDigits(505) == 3)
print(sumDigits(123456789) == 45)
print(sumDigits(0) == 0)


# # Optional Extra Problems
# ## Try these if you finish the other exercises early

# ## Question 7
# Write a recursive function `gcd(a, b)` that:
# 1. Takes two positive integers `a` and `b` as input.
# 2. Returns the **greatest common divisor** of `a` and `b`.
# 
# For example:
# ```
# gcd(15, 10)   == 5  # nothing bigger than 5 divides 15 and 10.
# gcd(24, 36)   == 12
# gcd(72, 180)  == 36
# gcd(101, 197) == 1  # 101 and 197 do not share any common factors.
# gcd(39793, 1) == 1  # gcd(a, 1) == 1 for all positive a.
# gcd(22, 0)    == 22 # gcd(a, 0) == a for all positive a.
# ```

# To implement `gcd()`, we will use a recursive algorithm that Euclid discovered in Alexandria, Egypt in 300BC. Here it is:
# 
# #### Recursive case
# If $b > 0$,
# `gcd(a, b) == gcd(b, a % b)`
# 
# #### Base case
# `gcd(a, 0) == a`
# 
# Here is an example of Euclid's algorithm for `gcd(180, 72)`:
# 
# ```
# # Recursive case: 180 % 72 == 36
# gcd(180, 72) == gcd(72, 36)
# 
# # Recursive case: 72 % 36  == 0
# gcd(72, 36) == gcd(36, 0)
# 
# # Base case (b == 0)
# gcd(36, 0) == 36
# ```
# 
# Result: the greatest common divisor of 180 and 72 is 36.
# 
# Here is another example, of `gcd(45, 210)`: 
# 
# ```
# # Recursive case: 45 % 210 == 45
# gcd(45, 210) == gcd(210, 45)
# 
# # Recursive case: 210 % 45 == 30
# gcd(210, 45) == gcd(45, 20)
# 
# # Recursive case: 45 % 30 == 15
# gcd(45, 30) == gcd(30, 15)
# 
# # Recursive case: 30 % 15 = 0
# gcd(30, 15) == gcd(15, 0)
# 
# # Base case (b == 0)
# gcd(15, 0) == 15 
# ```
# 
# Result: the greatest common divisor of 45 and 210 is 15.

# ### 7.1
# Using Euclid's algorithm, write code for `gcd(a, b)`

# In[18]:


def gcd(a, b):
    # YOUR CODE HERE
    return

# After you finish, these should all print True
print(gcd(15, 10)   == 5)
print(gcd(24, 36)   == 12)
print(gcd(72, 180)  == 36)
print(gcd(101, 197) == 1)
print(gcd(39793, 1) == 1)
print(gcd(22, 0)    == 22)


# ## Question 8
# **Fibonacci numbers** have many applications in nature and math. Here are the first 10 Fibonacci numbers:
# 
# ```
# fib(0) == 0
# fib(1) == 1
# fib(2) == 1
# fib(3) == 2
# fib(4) == 3
# fib(5) == 5
# fib(6) == 8
# fib(7) == 13
# fib(8) == 21
# fib(9) == 34
# ...
# ```
# 
# Can you see a pattern? Using math, we can define the $n^{th}$ Fibonacci  number, $F(n)$, using a recurrence:
# 
# $F(0) = 0$
# 
# $F(1) = 1$
# 
# and for $n >= 2$:
# 
# $F(n) = F(n - 1) + F(n - 2)$
# 
# ### 8.1
# Write code to find the $n^{th}$ Fibonacci number.

# In[27]:


def fib(n):
    # YOUR CODE HERE
    return

# When you finish, these should all print True
print(fib(0) == 0)
print(fib(1) == 1)
print(fib(2) == 1)
print(fib(3) == 2)
print(fib(6) == 8)
print(fib(9) == 34)
print(fib(20) == 6765)


# ## Question 9
# The decimal number system (base 10) is a common way to write numbers. Here we will explore the **binary number system** (base 2) which has many applications in computing. 
# 
# To give an example, 128 in decimal is written as 10000000 in binary. Here is why: 
# 
# In decimal (base 10),
# 
# $128 = 1 \cdot 10^2 + 2 \cdot 10^1 + 8 \cdot 10^0$
# 
# and in binary (base 2),
# 
# $128 = 1 \cdot 2^6 + 0 \cdot 2^5 + \dots + 0 \cdot 2^0$
# 
# Here is another example. 39 is 100111 in binary:
# 
# In decimal, 
# 
# $39 = 3 \cdot 10^1 + 9 \cdot 10^0$
# 
# and in binary,
# 
# $39 = 1 \cdot 2^5 + 0 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0$ 

# ### 9.1 
# Write a recursive function, `binaryString(n)`, that:
# * Takes an integer, `n`, as input.
# * Returns a string of 1s and 0s representing n in binary.
# 
# Hint: In python, `str(n)` converts a number to a string.
# * `str(1) == '1'`
# * `str(55) == '55'`

# In[37]:


def binaryString(n):
    # YOUR CODE HERE
    return

# After you finish, these should print True
testCases = [
    [0, '0'],
    [1, '1'],
    [2, '10'],
    [1, '1'],
    [2, '10'],
    [3, '11'],
    [4, '100'],
    [5, '101'],
    [6, '110'],
    [7, '111'],
    [8, '1000'],
    [39, '100111'],
    [128, '10000000'],
    [297371, '1001000100110011011'],   
]
for arg, result in testCases:
    print(binaryString(arg) == result)


# ### 9.2 
# Write a recursive function `decimalNumber(binString)` that converts a binary string `binString` into its corresponding decimal number. 
# 
# Hint: In Python, `int(decimalString)` converts a string into an integer:
# * `int('0') == 0`
# * `int('44') == 44`

# In[44]:


def decimalNumber(binString):
    # YOUR CODE HERE
    return None

testCases = [
    ['0', 0],
    ['1', 1],
    ['10', 2],
    ['1', 1],
    ['10', 2],
    ['11', 3],
    ['100', 4],
    ['101', 5],
    ['110', 6],
    ['111', 7],
    ['1000', 8],
    ['100111', 39],
    ['10000000', 128],
    ['1001000100110011011', 297371],   
]
for arg, result in testCases:
    print(decimalNumber(arg) == result)
print(decimalNumber(binaryString(12278)) == 12278)
print(binaryString(decimalNumber('100111')) == '100111')


# ## Question 10
# In mathematics, a **permutation** of a list is the same list, but in a different order. 
# 
# For example, `[0, 2, 1]` and `[2, 0, 1]` are both permutations of `[0, 1, 2]`.
# 
# Write a recursive function `permutations(n)` that takes an integer, `n`, as input, and returns a **sorted** list of all permutations of integers between `0` and `n`. Examples: 
# 
# ```
# permutations(0) == [[0]]
# 
# permutations(1) == [[0, 1], [1, 0]]
# 
# permutations(2) == [[0, 1, 2], [0, 2, 1], 
#                     [1, 0, 2], [1, 2, 0], 
#                     [2, 0, 1], [2, 1, 0]]
# 
# ```
# Hints
# * `myList.insert(5, 'myItem')` will insert `'myItem'` at position `5` in `myList`.
# * Use `sort(myList)` to put `myList` in sorted order. Note: `sort()` returns `None`, so use it on its own line of code. 
# * In problem 10, **it is OK to use loops too**.

# In[84]:


# Example code: insert() and sort()
myList = [2, 0, 3, 1]

myList.insert(2, 77) # insert 77 at position 2 in myList
print("myList hasn't been sorted yet:", myList)

myList.sort()
print("Now myList is sorted:", myList)


# ### 10.1 
# Write a recursive `permutations(n)` function. **Remember: it is OK to use loops in Question 10!**

# In[85]:


def permutations(n):
    return
    
# If your code is correct, these should all print True
print(permutations(0) == [[0]])
print(permutations(1) == [[0, 1], [1, 0]])

print(permutations(2) == [[0, 1, 2], [0, 2, 1], 
                          [1, 0, 2], [1, 2, 0], 
                          [2, 0, 1], [2, 1, 0]])

if permutations(0) != None:
    print(len(permutations(6)) == 5040)
    print(permutations(6)[3791] == [5, 1, 3, 6, 4, 2, 0])
else:
    print(False)


# In[ ]: