Fibonacci with Dict Memoization

Medium ⏱ 12 min 54% acceptance ★★★★☆ 4.3
Write a function fib_memo(n, memo=None) that returns the n-th Fibonacci number (fib(0)=0, fib(1)=1) using recursion with a dict-based memo cache to avoid recomputation. The cache must be a plain dict passed/reused across recursive calls.

Examples

Example 1
Input
fib_memo(10)
Output
55
Explanation

Standard Fibonacci sequence, 10th term is 55.

Example 2
Input
fib_memo(0)
Output
0
Explanation

Base case.

Constraints

  • n >= 0.
  • Must use a dict to cache already-computed results.

Topics

Dictionariesmemoization

Companies

GoogleApple

Hints

Hint 1

Default `memo = {}` on first call (careful with mutable default args — initialize inside if None).

Hint 2

Check `if n in memo: return memo[n]` before recursing.

← Nested Order Total Traversal Least Frequent Element →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.