In [ ]:

```
%config InteractiveShell.ast_node_interactivity="none"
```

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!
```

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

Often, we see recursive functions that return `list`

s or `int`

s or `float`

s or `string`

s. 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
```

**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
```

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
```

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
```

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 `string`

s.

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!
```

**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 [ ]:

```
```