Fibonacci sequence
- Algorithms course
- Beginner
- Lesson 41/80
- 4 min
Each number is the sum of the previous two in Fibonacci.
Fibonacci sequence
The Fibonacci sequence is a sequence where each number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
The first two numbers are 0 and 1. Each subsequent number is computed with F(n) = F(n-1) + F(n-2).
Recursive definition
Fibonacci's recursive definition: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). This translates directly to code.
However, this naive recursive solution is very slow because the same subproblem is computed many times.
Practice Recursive Fibonacci
Write fib(n). If n < 2 return n, else fib(n-1) + fib(n-2). Print 8 with print(fib(6)).
Starter code
def fib(n):
# Compute FibonacciSample solution
def fib(n):
# Compute Fibonacci
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(6))Expected output
8
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 How is each Fibonacci number found?
- Product
- Square of previous
- Random
- Sum of previous two Correct answer
Explanation: It is the sum of the previous two.
2 First value
F(0) = ____F(0) = 0Explanation: 0 is right.
3 Fibonacci sequence: match the terms
| Term | Meaning |
|---|---|
F(0) |
0 |
F(1) |
1 |
F(n) |
F(n-1)+F(n-2) |
F(2) |
0+1 |