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 \ge 2$:
$F(n) = F(n - 1) + F(n - 2)$
Task: Write code to find the $n^{th}$ Fibonacci number.
def fib(n):
# YOUR ANSWER HERE
pass
# 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)
Consider a recursive function called tribonacci(n)
:
Tribonacci numbers are like the Fibonacci numbers, but instead of starting with two predetermined terms, the sequence starts with three predetermined terms and each term afterwards is the sum of the preceding three terms. That is,
$\text{Tribonacci}(n) = \text{Tribonacci}(n-1) + \text{Tribonacci}(n-2) + \text{Tribonacci}(n-3)$
with $\text{Tribonacci}(0) = \text{Tribonacci}(1) = 0$ and $\text{Tribonacci}(2) = 1$
The first few tribonacci numbers are:
tribonacci(0) == 0
tribonacci(1) == 0
tribonacci(2) == 1
tribonacci(3) == 1
tribonacci(4) == 2
tribonacci(5) == 4
tribonacci(6) == 7
tribonacci(7) == 13
tribonacci(9) == 44
tribonacci(11) == 149
Implement tribonacci(num)
.
Hint: The base case includes 0, 1 and 2.
def tribonacci(n):
# your code here
pass
# after you finish, these all should print true
print('Test passed:', tribonacci(0) == 0)
print('Test passed:', tribonacci(1) == 0)
print('Test passed:', tribonacci(4) == 2)
print('Test passed:', tribonacci(5) == 4)
print('Test passed:', tribonacci(11) == 149)
The Catalan numbers count (among many other things) the number of parentheses expressions using n
correctly matched pairs of parentheses. (You will see these expressions in 9a_supp
.)
For example:
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
They are defined recursively as follows:
$$C_0 = 1$$$$C_{n+1} = \sum_{i=0}^n C_iC_{n-i}$$Write a function that computes $C_n$ given an input value n
. Use recursion!
def catalan(n):
# your code here
pass
# after you finish, these all should print true
print('Test passed:', catalan(0) == 1)
print('Test passed:', catalan(1) == 1)
print('Test passed:', catalan(2) == 2)
print('Test passed:', catalan(3) == 5)
print('Test passed:', catalan(5) == 42)
print('Test passed:', catalan(7) == 429)
Task: Write the function print_list(lst)
that prints out all the words in a nested list.
For example, if we have
lst = [["hello"], "darkness", ["my", "old", ["friend"]]]
it should give
hello
darkness
my
old
friend
Hint: In your function, use a for
loop to go through the list. Then:
x
is a list (type(x) == list
), call your function print_list
recursively with x
as the argument.x
(This is the base case)def print_list(lst):
# your code here
pass
# Test your code here
print_list([["hello"], "darkness", ["my", "old", ["friend"]]])
Consider a recursive function called nestedListSum(nestedList)
:
nestedList
, which can contain either integers or nested lists.For example:
nestedListSum([1, 2, 3, [4, 5]]) == 15
nestedListSum([[1, 2], [3, [4, 5]]]) == 15
nestedListSum([1, [2, [3, [4, [5]]]]]) == 15
Implement nestedListSum(nestedList)
.
Hint: Use the same type
check as in the previous question.
def nestedListSum(nestedList):
# your code here
pass
# after you finish, these all should print true
print('Test passed:', nestedListSum([]) == 0)
print('Test passed:', nestedListSum([1, 2, 3, [4, 5]]) == 15)
print('Test passed:', nestedListSum([[1, 2], [3, [4, 5]]]) == 15)
print('Test passed:', nestedListSum([1, [2, [3, [4, [5]]]]]) == 15)
In this exercise, we want to use recursion to create a flood-fill function for images. Our flood-fill function is supposed to fill a connected region of black pixels with a different color.
For example, if we do flood-fill with red color on the center of this image:
the region containing the center pixel becomes red:
We first start with a function generating black-white noise images that we can use to test our function on later. Run the code below.
from simpleimage import SimpleImage
import random
def get_random_image(size, threshold):
image = SimpleImage.blank(size, size)
for y in range(size):
for x in range(size):
if random.random() > threshold:
image.set_rgb(x, y, 0, 0, 0)
return image
image = get_random_image(50, 0.7)
image.show(resize_width=200)
Exercise: Now fill in the floodfill(img, x, y, r, g, b)
function below. Its parameters are:
img
to do the flood-fill onx
and y
r
, g
and b
components of the color to fill in.Whenever we find a black pixel, we fill it with the new color and then do the same flood-fill procedure for the neighbors of our pixel, to expand the region we are filling in.
Hint: Proceed as follows:
img.set_rgb
floodfill
for the pixels at $(x-1, y)$, $(x+1, y)$, $(x, y-1)$ and $(x, y+1)$.def floodfill(img, x, y, r, g, b):
# Your code here!
# This code tests your function on a 15x15 random image
image = get_random_image(15, 0.45)
image.set_rgb(7, 7, 0, 0, 0) # Make sure the center pixel is black
image.show(resize_width=200) # Show image before flood-fill
floodfill(image, 7, 7, 255, 0, 0) # Do flood-fill at the center.
image.show(resize_width=200) # Show image after flood-fill
Write a function, robotGrid(m, n)
that calculates the number of unique paths a robot placed at the top-left corner of a m x n
grid can take to reach the bottom-right corner. The robot can only move either down or right at any point in time.
For example:
robotGrid(0, 0) == 1
# Explanation: There is only one way to reach the bottom-right corner of a 0 x 0 grid.
robotGrid(1, 1) == 2
# Explanation: There are two ways to reach the bottom-right corner of a 1 x 1 grid.
# 1. Right -> Down
# 2. Down -> Right
robotGrid(2, 2) == 6
# Explanation: There are six ways to reach the bottom-right corner of a 2 x 2 grid.
# 1. Right -> Right -> Down -> Down
# 2. Right -> Down -> Right -> Down
# 3. Right -> Down -> Down -> Right
# 4. Down -> Right -> Right -> Down
# 5. Down -> Right -> Down -> Right
# 6. Down -> Down -> Right -> Right
Implement robotGrid(m, n)
recursively.
Hint: If we know the number of unique paths to the point $(m-1, n)$ and $(m, n-1)$, how can this help us compute the number of unique paths to $(m, n)$?
def robotGrid(m, n):
# your code here
pass
# after you finish, these all should print true
print('Test passed:', robotGrid(0, 0) == 1)
print('Test passed:', robotGrid(1, 1) == 2)
print('Test passed:', robotGrid(1, 2) == 3)
print('Test passed:', robotGrid(2, 2) == 6)
print('Test passed:', robotGrid(3, 2) == 10)
Write a Python program to calculate the harmonic sum of n
.
Note: The harmonic sum is the sum of reciprocals of the positive integers.
Examples:
harmonic_sum(1) == 1
harmonic_sum(2) == (1 + 1/2)
harmonic_sum(3) == (1 + 1/2 + 1/3)
harmonic_sum(4) == (1 + 1/2 + 1/3 + 1/4)
Implement harmonic_sum(n)
.
def harmonic_sum(n):
# Your code here
pass
# test your code here
print('Test passed:', harmonic_sum(7) == 1 + 1 / 2 + 1 / 3 + 1 / 4 + 1 / 5 + 1 / 6 + 1 / 7)
print('Test passed:', harmonic_sum(4) == 1 + 1 / 2 + 1 / 3 + 1 / 4)
print('Test passed:', harmonic_sum(5) == 1 + 1 / 2 + 1 / 3 + 1 / 4 + 1 / 5)