Fibonacci with a Memo Dictionary

Hard ⏱ 18 min 34% acceptance ★★★★☆ 4.4
Implement fib_memo(n, memo=None) that computes the nth Fibonacci number using recursion plus a memo dictionary to cache previously computed results, avoiding the exponential blow-up of plain recursive Fibonacci. It must remain recursive — do not rewrite it as an iterative loop.

Examples

Example 1
Input
fib_memo(30)
Output
832040
Explanation

Runs instantly thanks to the cache, unlike naive recursion.

Example 2
Input
fib_memo(1)
Output
1
Explanation

Base case.

Constraints

  • 0 <= n <= 100
  • Must cache results in a dict and reuse them on repeated sub-calls.

Topics

RecursionOptimization

Companies

NetflixAirbnbLinkedIn

Hints

Hint 1

Use a mutable default sentinel: `memo=None`, then `if memo is None: memo = {}` inside the function.

Hint 2

Before recursing, check `if n in memo: return memo[n]`.

Hint 3

Store each computed result in memo before returning it.

← Even/Odd Check via Mutual Recursion Binary Search, Recursively →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.