Summary - Fibonacci

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.

Exercise Fibonacci (loop)

Write fib_iter(n). Compute Fibonacci with a loop. Print 13 with print(fib_iter(7)).

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

Test yourself

Summary - Fibonacci: match the terms

Fibonacci

Sum of previous two
F(0)=0

Base
F(1)=1

Second base
O(2^n)

Naive

Fibonacci formula

F(n) = F(n-1) + ____

Show answer

F(n) = F(n-1) + F(n-2)

What is the complexity of naive recursive Fibonacci?
- O(n)
- O(n log n)
- O(2^n)
- O(n^2)
Show answer

O(2^n) — O(2^n) is exponential.

Next lesson: Factorial definition

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies