In [ ]:

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

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

In [ ]:

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

In [ ]:

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

Above, the staff created a function called `repeat_print()`

. Below, use the function `repeat_print()`

to print out the string `'abc'`

, `5`

times.

In [ ]:

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

In [ ]:

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

In [ ]:

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

In [ ]:

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

In [ ]:

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

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

What is the base case for `sum_all()`

? Describe your answer using English.

In [ ]:

```
```

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.

In [ ]:

```
```

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

function

In [ ]:

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

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.

What is the base case for `num_times()`

?

In [ ]:

```
```

What is the recursive case for `num_times()`

?

In [ ]:

```
```

Write a `num_times()`

function using your base and recursive cases.

In [ ]:

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

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$:

- $a^0 = 1$
- $a^b = a \cdot a^{b-1}$

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

?

In [ ]:

```
#
```

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

?

In [ ]:

```
#
```

Write code for `exp(a, b)`

In [ ]:

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

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

What is the base case for `reverse(s)`

?

In [ ]:

```
#
```

What is the recursive case for `reverse(s)`

?

In [ ]:

```
#
```

Write code for `reverse(s)`

In [ ]:

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

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.

In [ ]:

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

Define a **recursive** function called `sum_digits(n)`

which:

- Takes an int
`n`

as an argument. Assume`n >= 0`

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

In [ ]:

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

Write a recursive function `gcd(a, b)`

that:

- Takes two positive integers
`a`

and`b`

as input. - 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:

If $b > 0$,
`gcd(a, b) == gcd(b, a % b)`

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

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

In [ ]:

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

**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)$

Write code to find the $n^{th}$ Fibonacci number.

In [ ]:

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

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$

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

In [ ]:

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

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`

In [ ]:

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

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

In [ ]:

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

Write a recursive `permutations(n)`

function. **Remember: it is OK to use loops in Question 10!**

In [ ]:

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