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)
Hello AddisCoder
Hello AddisCoder
Hello AddisCoder
Recursion is the best
Recursion is the best
Recursion is the best
Recursion is the best
Recursion is the best
Recursion is the best
Recursion is the best
Recursion is the best

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)
False
False
False
False

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)
False
False
False
False
False

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)
False
False
False
False
False
False

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('') == '')
False
False
False
False

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')
False
False
False
False
False

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)
False
False
False
False
False

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)
False
False
False
False
False
False

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)
False
False
False
False
False
False
False

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)
False
False
False
False
False
False
False
False
False
False
False
False
False
False

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')
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False

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)
myList hasn't been sorted yet: [2, 0, 77, 3, 1]
Now myList is sorted: [0, 1, 2, 3, 77]

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)
False
False
False
False