Recursive Fibonacci
- Algorithms course
- Beginner
- Lesson 42/80
- 4 min
Write a recursive Fibonacci function.
Base case
Fibonacci has two base cases: F(0) = 0 and F(1) = 1. These two values are known directly and stop the recursion.
Having two base cases ensures the function always terminates. Each call decreases n and eventually reaches 0 or 1.
Complexity
Naive recursive Fibonacci has complexity O(2^n). This is exponential growth because each call makes two sub-calls.
For n=40, billions of calls are made. This shows why naive recursion is slow. Memoization solves this problem.
Practice Small Fibonacci
Write fib_small(n). If n=0 return 0, if n=1 return 1. Print 1 with print(fib_small(1)).
Starter code
def fib_small(n):
# Small FibonacciSample solution
def fib_small(n):
# Small Fibonacci
if n == 0:
return 0
if n == 1:
return 1
print(fib_small(1))Expected output
1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Second base
Question
F(1) = ____
Answer
F(1) = 1Explanation: 1 is right.
2 Recursive Fibonacci: match the terms
| Term | Meaning |
|---|---|
F(0)=0 |
Base |
F(1)=1 |
Second base |
O(2^n) |
Naive |
Two calls |
Exponential |
3 What is the complexity of naive recursive Fibonacci?
- O(log n)
- O(n^2)
- O(2^n) Correct answer
- O(n)
Explanation: O(2^n) is exponential growth.