Call tree
- Algorithms course
- Beginner
- Lesson 43/80
- 4 min
Recursive Fibonacci repeats calls and is inefficient.
Call tree
Recursive Fibonacci's call tree is a binary tree where each node has two children. The same values are computed many times.
For example, fib(5) computes fib(3) twice and fib(2) three times. This repetition is the cause of exponential complexity.
Repetition problem
Naive Fibonacci's biggest problem is recomputing the same subproblems. fib(3) is called by both fib(4) and fib(5).
This repetition is solved at a more advanced level with memoization. Computed values are cached and not recomputed.
Practice Fibonacci list
Write fib_list(n). Return a list of n+1 Fibonacci numbers. Print [0, 1, 1, 2, 3, 5] with print(fib_list(5)).
Starter code
def fib_list(n):
# Fibonacci listSample solution
def fib_list(n):
# Fibonacci list
if n == 0:
return [0]
result = [0, 1]
for i in range(2, n + 1):
result.append(result[i-1] + result[i-2])
return result
print(fib_list(5))Expected output
[0, 1, 1, 2, 3, 5]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Call tree: match the terms
| Term | Meaning |
|---|---|
Call tree |
Binary tree |
Repetition |
Exponential growth |
fib(3) |
Twice |
Memoization |
Cache |
2 Why is naive Fibonacci slow?
- Few calls
- Recomputes same subproblems Correct answer
- Uses little memory
- No loop
Explanation: It recomputes the same subproblems.
3 Repetition
The same subproblem is computed ____.The same subproblem is computed repeatedly.Explanation: repeatedly is right.