JamCoders

 💾 Download
In [ ]:
%config InteractiveShell.ast_node_interactivity="none"

Week 2 day 2, Part 2 Exercises

Question 0: Definitions and Examples

Starting from the basics

What is recursion? Answer in words, and give an example (either in words or in code)

In [ ]:
# Answer here!

What is a base case? If unsure, refer to question 0.5 in the previous lab

In [ ]:
# Answer here!

What is a recursive case?

In [ ]:
# Answer here!

Question 1: List slicing and warm up

Some warm up, since the AC is so cold!

In recursion, we often have to split the inputs into different parts.

For example, sometimes we might break the input in half and call the function on both halves. Sometimes we might take break the input to handle the first thing, and then recursively call the function on the rest of the input.

So, we will practice with slicing

Note: pass does not do anything. You can delete it

Write a function to return the first element of a list

In [ ]:
def first_element(lst):
  """
  Input: lst (list)
  Output: (str, list, int) [first element of lst]
  """
  # Your code here!
  pass

# Use your function here to test that the function returns the first element of the list

Write a function to return everything except the first element of a list

In [ ]:
def except_first(lst):
  """
  Input: lst (list)
  Output: (list)
  """
  # Your code here!
  pass

# Use your function here to test that the function returns everything except the first element of the list

Write a function to return everything in the first half of the list. If there is an odd number, make the first half one less than the remaining second half.

For example, for the list [1, 2, 3, 4, 5, 6, 7], the first half should return [1, 2, 3]

In [ ]:
def first_half(lst):
  """
  Input: lst (list)
  Output: (list)
  """
  # Your code here!
  pass

# Use your function here to test that the function returns everything except the first element of the list

Write a function to return everything in the second half of the list. If there is an odd number, make the second half that you return have one more element than the first half.

For example, for the list [1, 2, 3, 4, 5, 6, 7], the second half should return [4, 5, 6, 7]

In [ ]:
def second_half(lst):
  """
  Input: lst (list)
  Output: (list)
  """
  #Your code here!
  pass

# Use your function here to test that the function returns everything except the first element of the list

Modify your code if needed, or verify that your code for first_element(), except_first(), first_half(), second_half() also work for strings!

In [ ]:
# Test here!

test_string = 'jam_coders'
print(first_element(test_string))
print(except_first(test_string))
print(first_half(test_string))
print(second_half(test_string))

None
None
None
None

Question 2: Boolean Recursion

Often, we see recursive functions that return lists or ints or floats or strings. However, sometimes we see recursions that return boolean values!

In this question, we will use recursion to write a function called is_in(lst, item) that takes in a list called lst and returns True if the item is in the lst, and False otherwise

Side note: You may think that most of the examples you have seen of recursion can be easily replaced with different code. For example, here, without recursion we can simply say:

def is_in(lst, item):
  return (item in lst)

However, many times recursion is more natural. We are doing this example in preparation for other lectures and exercises to come!

There are many ways to write this function, but let's do it recursively. For the first base case, what should we return (True or False) if lst is empty?

In [ ]:
# Answer in words, and write the if statement in code

For the second base case, should we return True or False if the first element lst[0] == item?

In [ ]:
# Answer in words, and write the if statement in code

For the recursive case, suppose that we know that the first element is not the item. How can we call is_in(lst, item) to check the remainder of the list, excluding the first element that we already know is not the item?

In other words, we already know the first element is not the item, or else we would have triggered the second base case. So, we can call is_in() using the lst without the first element, searching for the same item as before.

In [ ]:
# Answer in words, and write the recursive call is_in() in code

Now we are ready to write the function!

*Note: This question heavily relies on the list slicing from question 1, and you may use your previous functions if you'd like. These functions include: first_element(), except_first(), first_half(), second_half().

In [ ]:
def is_in(lst, item):
  """
  Input: lst (list), item (str, list, int)
  Output: (boolean) [if item is in lst]
  """

  # ===First base case===: the list has length zero so we return False
  if #FILL ME IN: 
    return False

  first_item = # Get the first item

  # ===Second base case===: the first thing in the list is the item we are searching for. 
  if #FILL ME IN:
    return True

  rest_of_list = # Get the rest of the list

  # ===Recursive case===: we search for the item in the rest of the list
  return #is_in(FILL ME IN)

print(is_in([1, 2, 3], 3))             # True
print(is_in(['j', 'c', 22], 'c'))      # True
print(is_in(['r', 2, 'hello'], 'bye')) # False

  File "<ipython-input-21-f441e91096f3>", line 4
    if #FILL ME IN:
                    ^
SyntaxError: invalid syntax

challenge - optional

The rest of the question is a challenge problem. For the next part of the question, Elijah wants to write is_in2(lst, item) that does the same thing as is_in(lst, item), except it follows a different logic:

  • if the length of the lst is 0, return False because item is not in an empty list.
  • if the length of the lst is 1 and the element is item (In otherwords, lst[0] == item), then we have found the element and return True.
  • call is_in2() on the first half of lst, keeping track of the return boolean value.
  • call is_in2() on the second half of lst, keeping track of the return boolean value.
  • return True if the value is either in the first half of lst or the second half of lst, and False otherwise.

Explain in words why the logic above makes sense. This is the most important part of the question, so please ask us to explain this recursion to you before you move on if you are not sure!

In [ ]:
# Write your answer in words here!

In words, what are the base cases and recursive case?

In [ ]:
# Write your answer in words here!

Now code is_in2(lst, item)

In [ ]:
def is_in2(lst, item):
  """
  Input: lst (list), item (str, list, int)
  Output: (boolean) [if item is in lst]
  """
  # Your code here!

  # A summary of the key steps:
  # 1. handle the empty list
  # 2. handle the list with a single element
  # 3. split the list into two halves (we have already handled the case of an empty list)
  # 4. return True if the item is either in the left, OR in the right!

  pass

# Test your code here!
print(is_in([1, 2, 3], 3))             # True
print(is_in(['j', 'c', 22], 'c'))      # True
print(is_in(['r', 2, 'hello'], 'bye')) # False

Question 3: Ping Pong

Anakai and Michael like playing ping pong together (this may or may not be true). Let's write functions to play ping pong!

Help Anakai write a function called ping(n):

  • if n == 0, then return
  • ping(n) should print('ping') then call pong(n - 1)
  • you haven't written pong() yet, but we will write that next!
In [ ]:
def ping(n):
  """
  Input: n (int)
  Output: (None)
  """
  # if n == 0, return
  # print 'ping'
  # call pong(n - 1)
  pass

Help Michael write a function called pong(n):

  • if n == 0, then return
  • pong(n) should print('pong') then call ping(n - 1)
  • you have already written ping()!

if you call both ping(n) and pong(n), you will go into an infinite loop. Make sure you are calling ping(n - 1) and pong(n - 1). You will also go into an infinite loop if you forget the base case

In [ ]:
def pong(n):
  """
  Input: n (int)
  Output: (None)
  """
  # if n == 0, return
  # print 'pong'
  # call ping(n - 1)

Try running ping(5). Can you explain what happens and why?

In [ ]:
# run ping(5). What happens, and why?

What are the base and recursive cases?

In [ ]:
# explain the base and recursive cases in words

This may be confusing, so the rest of this problem is optional

Natnael watches them play, and notices that he knows how long the game will last just by looking at n. He thinks this is bad because there is no skill involved. So, he writes a function called is_success(n) that will return True with n percent chance.

Run his code a few times to understand how is_success(n) works

In [ ]:
# Run this a few times to understand how is_success(n) works
from random import randrange

# Here is Natnael's code
def is_success(n):
  """
  Input: n (int) [percent out of 100]
  Output: (boolean) [True with probability n/100]
  """
  return randrange(100) < n

# Here is how you could use it. 
print(is_success(30))
print(is_success(40))
print(is_success(50))
print(is_success(60))
print(is_success(70))

Create ping_skillz(p, q) and pong_skillz(p, q). Use is_success so that with n percent chance, they call the other function.

For ping_skillz(p, q):

  • with p percent chance: print 'ping!' and call pong(p, q)
  • with 100 - p percent chance: print 'ping failed' and return

For pong_skillz(p, q):

  • with q percent chance: print 'pong!' and call ping(p, q)
  • with 100 - q percent chance: print 'pong failed' and return
In [ ]:
def ping_skillz(p, q):
  """
  Input: p (float) [success for ping], q (float) [success for pong]
  Output: (None)
  """
  # Code here! Remember to use is_success to check if we successfully went to pong() or not!
  pass

def pong_skillz(p, q):
  """
  Input: p (float) [success for ping], q (float) [success for pong]
  Output: (None)
  """
  # Code here! Remember to use is_success to check if we sucessfully went to ping() or not!
  pass

# Test your code here!

very, very optional

Run ping_skillz(0.5, 0.5) ten times, recording the average number of combined ping!s and pong!s. On average, how many combined ping!s and pong!s are printed out?

You can manually run it 10 times and calculate the sum (which we recommend), or you can write a function to help if you have extra time.

In [ ]:
# Your answer for the average number. Feel free to show your calculation eg:
# print( (1 + 0 + 2 + 0 ... ) / 10 )

very, very, very optional

The following is extremely challenging brain teaser that you should save for the end of the lab and attempt only if you have time.

Can you use math to reason about why you got the answer above? That is, if p == q == 0.5, how many combined ping!s and pong!s would you expect to see printed on average?

In [ ]:
# Explain your reasoning and any math you used

Question 4: Repetition

More exercises!

Write a recursive function print_natural(n) to print out the first n natural numbers in descending order. The logic is:

  • if n <= 0 then we're done. return
  • otherwise, print(n), and recursively call print_natural()

Hint: what should be the argument in the recursive call to print_natural()?

What is the base case? What is the recursive case?

In [ ]:
# A few words here, be short so you can finish this quickly!

Write the function below

In [ ]:
def print_natural(n):
  """
  Input: n (int) [largest natural number to print]
  Output: (None)
  """
  # Your code here
  pass

# Test here

Write a recursive function sum(n) to return out the sum of the first n natural numbers. You may have seen this iteratively before in a previous lab, so this is some extra repetition with recursion! Identify the base case and recursive case.

In [ ]:
# A few words here

Write the function:

In [ ]:
def sum(n):
  """
  Input: n (int)
  Output: (int) [1 + 2 + ... + n]
  """
  # Your code here

  # Make sure you have a logical base case so that you don't have an infinite loop!
  pass

# Test here

Question 5: Palindrome Revisisted

Recall we had an entire lecture on palindromes. You may have noticed that a palindrome is like an onion. You may think that is because they both stink. But there is yet another similarity: you can peel the palindrome layer by layer.

For example: Suppose you wanted to check if 'racecar' is a palindrome. You could look at the first and last letter, and if they are the same, recursively check the rest of the string to see if 'aceca' is a palindrome. You could keep on peeling away the first and last letters layer by layer until you have a single letter e, which is a palindrome.

Just as we have done before, brainstorm the logic of the function below

In [ ]:
# What are the base cases?

# What are the recursive cases?

# Write some tentative logic for how the code will work in words

Try to code the recursive function is_palindrome(string) that returns True if string is a palindrome, and False otherwise. Make sure it works for both even and odd length strings.

In [ ]:
def is_palindrome(string):
  """
  Input: string (str)
  Output: (boolean) [True if palindrome]
  """

  # Your code here

  # What is the base case?

  # What is the recursive case?
  pass

# Test some palindromes here!

Question 6: Challenge!

This is a very challenging problem. We recommend finishing notebook a before trying this question

Given a positive integer n, print all combinations of numbers between 1 and n having sum n.

For example print_combinations(5): the following combinations are possible:

[ 5 ]
[ 1, 4 ]
[ 2, 3 ]
[ 1, 1, 3 ]
[ 1, 2, 2 ]
[ 1, 1, 1, 2 ]
[ 1, 1, 1, 1, 1 ]

Hint 1: This is a question where recursion may be more natural than other methods.

Hint 2: Consider instead coding a function: print_comb(start, stop, cur, output) that prints all combinations of numbers from start to stop that sum to output, assuming we have already taken all the numbers in the list cur.

In [ ]:
# Required
def print_combinations(n):
  """
  Input: n (int)
  Output: (None)
  """
  pass

# Recommended, delete if you don't use
def print_comb(start, stop, cur, output):
  pass

# Test here

double extra challenge:

Can you return the results in a list of lists?

In [ ]: