Fibonacci¶
In this exercise, we will write a function fibonacci which takes a number n and outputs the nth number in the Fibonacci sequence.
The Fibonacci Sequence¶
Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones.
That is, the $n$th number in the Fibonacci Sequence, $F_{n}$ is defined as:
$F_{n} = F_{n-1} + F_{n-2}$
Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn . The sequence commonly starts from 0 and 1.
For the purpose of this exercise we will say:
- $F_{0} = 0$
- $F_{1} = 1$
- $F_{2} = 1$
- $F_{3} = 2$
- $F_{4} = 3$
- $F_{5} = 5$
- $F_{6} = 8$
- ...
Your Assigment¶
For your assignment, write a function fibonacci(n) which will output the value of the $n$th Fibonacci number.
For this problem, you should expect your function to explicitly handle the cases where n is 0 and n is 1. But, for all values of n greater than 1, your function should be able to compute $F_{n}$.
This problem is tricky and there are multiple ways to solve it! Don't feel discouraged!
Test Cases¶
Here are some test code that your function should pass (feel free to copy-paste this into the bottom of your code to test):
f_0 = fibonacci(0)
print(f"fibonacci(0);\texpected: 0,\tgot: {f_0}")
f_1 = fibonacci(1)
print(f"fibonacci(1);\texpected: 1,\tgot: {f_1}")
f_6 = fibonacci(6)
print(f"fibonacci(6);\texpected: 8,\tgot: {f_6}")
f_11 = fibonacci(11)
print(f"fibonacci(11);\texpected: 89,\tgot: {f_11}")
f_19 = fibonacci(19)
print(f"fibonacci(19);\texpected: 4181,\tgot: {f_19}")
# def fibonacci(n):
# if n == 0:
# return 0
# if n == 1:
# return 1
# f_prev_prev = 0
# f_prev = 1
# i = 1
# while i < n:
# f_curr = f_prev + f_prev_prev
# f_prev_prev = f_prev
# f_prev = f_curr
# i += 1
# return f_curr
# F_{n} = F_{n-1} + F_{n-2}
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n-1) + fibonacci(n-2)
f_0 = fibonacci(0)
print(f"fibonacci(0);\texpected: 0,\tgot: {f_0}")
f_1 = fibonacci(1)
print(f"fibonacci(1);\texpected: 1,\tgot: {f_1}")
f_2 = fibonacci(2)
print(f"fibonacci(2);\texpected: 1,\tgot: {f_1}")
f_6 = fibonacci(6)
print(f"fibonacci(6);\texpected: 8,\tgot: {f_6}")
f_11 = fibonacci(11)
print(f"fibonacci(11);\texpected: 89,\tgot: {f_11}")
f_19 = fibonacci(19)
print(f"fibonacci(19);\texpected: 4181,\tgot: {f_19}")
fibonacci(0); expected: 0, got: 0 fibonacci(1); expected: 1, got: 1 fibonacci(2); expected: 1, got: 1 fibonacci(6); expected: 8, got: 8 fibonacci(11); expected: 89, got: 89 fibonacci(19); expected: 4181, got: 4181