Call tree

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.

Exercise 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)).

Show example 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))

Test yourself

Call tree: match the terms

Call tree

Binary tree
Repetition

Exponential growth
fib(3)

Twice
Memoization

Cache
Why is naive Fibonacci slow?
- Few calls
- Recomputes same subproblems
- Uses little memory
- No loop
Show answer

Recomputes same subproblems — It recomputes the same subproblems.

Repetition

The same subproblem is computed ____.

Show answer

The same subproblem is computed repeatedly.

Next lesson: Summary - Fibonacci

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies