JamCoders

💾 Download

%config InteractiveShell.ast_node_interactivity="none"

Week 2 day 2, Part 1 Exercises

DO NOT USE FOR LOOPS OR WHILE LOOPS

Question 0: Definitions and Examples

0.1

Please read the following instance of recursion.

Sometimes a function can use itself. Look closely at the first and last line of the function below:

def f(x):
  if x <= 0:
    return x
  else:
    return f(x - 1) + 1

Notice that we are making a new function called f in the first line, but we also use the function f in the last line of f. In a way, the function f uses itself. This is called recursion.

In your own words, summarize what recursion is, and take a guess at what f does.

# Summarize what recursion is in a comment here!

0.2

Suppose we wanted to use this idea of recursion to print some text, some number of times . Let's see how we could to this in the code below.

Read the code below slowly, then run it. Focus on the line commented: # THIS LINE CAUSES THE RECURSION

def repeat_print(text, how_many_to_print):
    """
    Input: text (str) [text to repeat], how_many_to_print (int) [times to repeat]
    Output: (None)
    """

    # If we want to print zero times, then just return
    if how_many_to_print == 0:
        return

    # Otherwise...
    else:
        print(text)
        # Since we just printed it out once, we want to print the text out one less time now.
        repeat_print(text, how_many_to_print - 1) # THIS LINE CAUSES THE RECURSION


repeat_print('Hello JamCoder', 3)
repeat_print('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

Above, the staff created a function called repeat_print(). Below, use the function repeat_print() to print out the string 'abc', 5 times.

# Use the function repeat_print() to print out out 'abc'

0.3

Below, use the function repeat_print() to print out the string 'jam', 6` times.

# Use the function repeat_print() to print out 'jam'

0.4

Here is an example of what happens when we call repeat_print('coders', 5):

When we call repeat_print('coders', 5):

• We are in repeat_print(coders, 5), so we print the text which is print('coders'), then call repeat_print('coders', 5 - 1)
• We are in repeat_print(coders, 4), so we print the text which is print('coders'), then call repeat_print('coders', 4 - 1)
• We are in repeat_print(coders, 3), so we print the text which is print('coders'), then call repeat_print('coders', 3 - 1)
• We are in repeat_print(coders, 2), so we print the text which is print('coders'), then call repeat_print('coders', 2 - 1)
• We are in repeat_print(coders, 1), so we print the text which is print('coders'), then call repeat_print('coders', 1 - 1)
• We are in repeat_print(coders, 0)then we get how_many_to_print == 0, so we return

The same as we have done above, can you explain in words what happens when we call repeat_print('zxcv', 5)?

# We have shown what happens when someone uses the function and calls `repeat_print('coders', 5)`. 
# What happens when someone uses the function and calls `repeat_print('zxcv', 5)?`

0.5

Important: Read the following definitions:

• In recursion, a base case is a case (or branch) where we do not use the function again.
• a recursive case is a case (or branch) where we do use the function again.

For example, in the repeat_print() function, the base case is when how_many_to_print == 0. Then, we return without calling repeat_print() again.

The recursive case is when how_many_to_print > 0. Then we call repeat_print(text, how_many_to_print - 1)

Explain in your own words what the base case is and what the recursive case is for repeat_print(), and why.

# Explain what the base case is. Explain what the recursive case it. Explain why

0.6

Elijah wrote the repeat_print() function, but Jabari says he has a better way. Check out his code!

def repeat_print2(text, how_many_to_print):
  """
    Input: text (str) [text to repeat], how_many_to_print (int) [times to repeat]
    Output: (None)
    """

  # Do the following how_many_to_print number of times:
  for i in range(how_many_to_print):
    # Print the text
    print(text)

Do repeat_print() and repeat_print2() do the same thing? Based on this, would you say that sometimes there are different ways to approach the same problem?

# Answer here: do they do the same thing? Are there multiple ways to create the same function?

Question 1: sum_all(lst)

Consider a recursive function called sum_all(lst).

• It takes a list of numbers, lst, as input.
• It returns the sum of the list.

For example:

sum_all([1, 1, 1]) == 3
sum_all([1, 2, 3]) == 6
sum_all([]) == 0
sum_all([1, -1]) == 0

1.1

What is the base case for sum_all()? Describe your answer using English.

1.2

Remember that Question 0.5 has the definition for base cases and recursive cases.

What is the recursive case for sum_all()? Describe your answer using English.

1.3

Use your base case and recursive case to write the sum_all() function

def sum_all(lst):
    """Returns the sum of all items in a list
    Input: lst(list)
    Output: (int) [sum of elements in lst]
    """

    # CHECK IF INPUT MATCHES THE BASE CASE
      # RETURN BASE CASE SOLUTION
    
    # ELSE, RETURN RECURSIVE CASE SOLUTION


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

Question 2: num_times()

Consider a recursive function called num_times(s, letter):

• It takes a string s and a single letter letter.
• It returns how many times letter appears in s.

For example:

num_times('aaabbaaab', 'b') == 3
num_times('aaabbaaab', 'a') == 6
num_times('c', 'c') == 1
num_times('abcd', 'e') == 0
num_times('', 'a') == 0

Remember that Question 0.5 has the definition for base cases and recursive cases.

2.1

What is the base case for num_times()?

2.2

What is the recursive case for num_times()?

2.3

Write a num_times() function using your base and recursive cases.

def num_times(s, letter):
    """Returns the number of times a letter appears in a string
    Input: s(str), letter(str)
    Output: (str) [count of letter in s]
    """
    # YOUR ANSWER HERE


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

Question 3: exp()

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

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

#

3.2

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

#

3.3

Write code for exp(a, b)

def exp(a, b):
    # YOUR ANSWER HERE
    """
    Input: a (int),  b (int)
    Output: (int) [a to the power of b]
    """


    # 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: reverse()

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 base case for reverse(s)?

#

4.2

What is the recursive case for reverse(s)?

#

4.3

Write code for reverse(s)

def reverse(s):
    """
    Input: s (str)
    Output: (str) [s reversed]
    """
    # YOUR ANSWER HERE
    

    # 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: remove_letter()

Define a recursive function remove_letter(s, letter) which:

• Takes a string s and a single character letter.
• Returns the string back without the given letter. Our function should remove every copy of that letter.

def remove_letter(s, letter):
  """
  Input: s (str), letter (str)
  Output: (str) [s without letter]
  """
  # YOUR ANSWER HERE

    


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

Question 6: sum_digits()

Define a recursive function called sum_digits(n) which:

1. Takes an int n as an argument. Assume n >= 0.
2. Returns the sum of the digits of n. For example:

sum_digits(111) == 3   # because 1 + 1 + 1 == 3
sum_digits(123) == 6   # because 1 + 2 + 3 == 6
sum_digits(505) == 10  # because 5 + 0 + 5 == 10

Hint: use the % and // operators

def sum_digits(n):
    """
    Input: n (int)
    Output: (int) [sum of digits in n]
    """
    # YOUR ANSWER HERE



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

Optional Challenge 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)

def gcd(a, b):
    """Returns the greatest common divisor  of two integers a and b
    Input: a (int), b (int)
    Output: (int) [the greatest common divisor]
    """
    # YOUR ANSWER HERE


# 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.

def fib(n):
    """Returns the nth Fibonacci number, F(n)
    Input: n (int)
    Output: (int) [F(n)]
    """
    # YOUR ANSWER HERE



# 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, binary_string(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'

def binary_string(n):
    """Takes an integer n and returns its binary representation
    Input: n (int)
    Output: (str) [binary representation]
    """
    # YOUR ANSWER HERE


    # After you finish, these should print True
test_cases = [
    [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 test_cases:
    print(binary_string(arg) == result)

9.2

Write a recursive function decimal_number(bin_string) that converts a binary string bin_string into its corresponding decimal number.

Hint: In Python, int(decimal_string) converts a string into an integer:

• int('0') == 0
• int('44') == 44

def decimal_number(bin_string):
    """Takes a binary string and returns the associated decimal representation
    Input: bin_string (str)
    Output: (str)
    """

    # YOUR ANSWER HERE

test_cases = [
    ['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 test_cases:
    print(decimal_number(arg) == result)
print(decimal_number(binary_string(12278)) == 12278)
print(binary_string(decimal_number('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

• my_list.insert(5, 'my_item') will insert 'my_item' at position 5 in my_list.
• Use sort(my_list) to put my_list 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.

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

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

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

10.1

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

def permutations(n):
    """Returns all permutations of the list [0, 1, 2, ..., n-1] from 1 to n.
    Input: n (int)
    Output: (list) [The permutations of the list]
    """"

    # YOUR ANSWER HERE


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