Summary - Fibonacci
- Algorithms course
- Beginner
- Lesson 44/80
- 4 min
Print the first n Fibonacci numbers in a mini task.
Summary - Fibonacci
In this group you learned the Fibonacci sequence, its recursive definition, base cases and the repetition problem. Naive solution is O(2^n).
Fibonacci shows the power and weakness of recursion: readable but recomputes. Memoization fixes this.
Practice Fibonacci (loop)
Write fib_iter(n). Compute Fibonacci with a loop. Print 13 with print(fib_iter(7)).
Starter code
def fib_iter(n):
# Fibonacci with loopSample solution
def fib_iter(n):
# Fibonacci with loop
if n < 2:
return n
a = 0
b = 1
for i in range(2, n + 1):
a, b = b, a + b
return b
print(fib_iter(7))Expected output
13
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Fibonacci: match the terms
| Term | Meaning |
|---|---|
Fibonacci |
Sum of previous two |
F(0)=0 |
Base |
F(1)=1 |
Second base |
O(2^n) |
Naive |
2 Fibonacci formula
Question
F(n) = F(n-1) + ____
Answer
F(n) = F(n-1) + F(n-2)Explanation: F(n-2) is right.
3 What is the complexity of naive recursive Fibonacci?
- O(n)
- O(n log n)
- O(2^n) Correct answer
- O(n^2)
Explanation: O(2^n) is exponential.