Fibonacci Number 15 XP Easy

LeetCode Ctrl+Enter Run Ctrl+S Save

The Fibonacci sequence: each number is the sum of the two before it.

# F(0) = 0, F(1) = 1
# F(n) = F(n-1) + F(n-2)
# 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The naive recursive solution is elegant but extremely slow:

def fib_slow(n):       # O(2^n) — DON'T USE!
    if n <= 1: return n
    return fib_slow(n-1) + fib_slow(n-2)

# fib_slow(40) takes SECONDS — it recomputes the same values billions of times!

The fix: Memoization — cache results of previous calls:

def fib_fast(n, memo={}):
    if n <= 1: return n
    if n in memo: return memo[n]
    memo[n] = fib_fast(n-1, memo) + fib_fast(n-2, memo)
    return memo[n]
# fib_fast(40) is instant — O(n) time!

This is your first taste of Dynamic Programming. Memoization = recursion + caching.

📋 Instructions

Implement `fibonacci(n)` with memoization. Print fibonacci for n = 0, 5, 10, 20.

Base cases: F(0)=0, F(1)=1. Use a dictionary as memo. Before computing, check if n is already in memo. After computing, store the result in memo.

🧪 Test Cases

Input

fibonacci(0)

Expected

0

Boundary value

Input

fibonacci(5)

Expected

5

Test case 2

Input

fibonacci(10)

Expected

55

Test case 3

Input

fibonacci(20)

Expected

6765

Test case 4

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›