Recursive Fibonacci with Memoization in Python
Plain recursive Fibonacci repeats the same work millions of times. Add a cache and it becomes instant.
- Writing Fibonacci recursively
- Why the plain version is exponential
- Memoization with functools.lru_cache
fib(4)fib(3)fib(2)fib(1)
fib(2)computed again
Remember answers you already computed
The problem
The recursive Fibonacci definition is beautiful but extremely slow: computing the 40th term repeats the same smaller calculations hundreds of millions of times. Memoization fixes this with one line and teaches a key idea of dynamic programming.
Think of it like this
Memoization is like a student who writes every answer in a notebook. When asked fib(5) again, they do not redo the work; they read the answer from the notebook. Each question is solved only once.
@cache📓 Keep a notebook of answersfibonacci(number - 1) + fibonacci(number - 2)🧮 Solve using two smaller questionsif number < 2: return number🛑 The first two answers are knownfibonacci(10)⚡ Every smaller answer is computed once: fastMemoization stores the result of each function call by its arguments, so repeated calls return the stored result instead of recomputing it.
Key points
if number < 2: return numbergives the first two terms, 0 and 1.fibonacci(number - 1) + fibonacci(number - 2)follows the definition directly.@cachefromfunctoolsremembers every result, so eachfibonacci(k)runs only once.- Without
@cache,fibonacci(10)would make 177 calls; with it, 11.
When should you use it?
- Recursive functions that repeat the same subproblems: paths in a grid, coin change, word splits.
- Learning the idea behind dynamic programming.
- Speeding up any pure function called often with the same arguments.
When not to use it
- Functions with side effects or results that change over time: the cache would return stale answers.
- Very deep recursion: even with a cache,
fib(5000)can exceed the recursion limit; a loop avoids that.
See how it works
Press Step to follow each call. Notice how fib calls the same smaller values again and again, which is why the plain version is slow.
Example code
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))
Result of running the code
55
Code explanation
The cache decorator remembers results by argument. This reduces the exponential naive recursion to O(n) time.
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Common mistakes
Recursion without a cache
The same values are recomputed again and again, and fib(40) takes many seconds.
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
Finished this lesson?
Mark it as learned to track your progress.
Practice with a challenge
Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.
- Fibonacci Number Return the n-th Fibonacci number. Easy
- Count Dice Sequences Count ordered die-roll sequences with a given total. Medium