Python Algorithms

Recursive Fibonacci with Memoization in Python

Plain recursive Fibonacci repeats the same work millions of times. Add a cache and it becomes instant.

  • Intermediate
  • 2 min read
  • 1 runnable example
What you'll learn
  • Writing Fibonacci recursively
  • Why the plain version is exponential
  • Memoization with functools.lru_cache
fib(4) without a cache
  • fib(4)
    • fib(3)
      • fib(2)
      • fib(1)
    • fib(2)computed again
With @lru_cache the second fib(2) is read from the cache. fib(10) = 55.

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.

From a notebook to code
@cache📓 Keep a notebook of answers
fibonacci(number - 1) + fibonacci(number - 2)🧮 Solve using two smaller questions
if number < 2: return number🛑 The first two answers are known
fibonacci(10)⚡ Every smaller answer is computed once: fast
Store each result the first time; reuse it afterwards.
In one sentence

Memoization stores the result of each function call by its arguments, so repeated calls return the stored result instead of recomputing it.

Key points

  1. if number < 2: return number gives the first two terms, 0 and 1.
  2. fibonacci(number - 1) + fibonacci(number - 2) follows the definition directly.
  3. @cache from functools remembers every result, so each fibonacci(k) runs only once.
  4. 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

Run code →
main.py
from functools import cache

@cache
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

print(fibonacci(10))
Get a Run button for this example

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.

  1. Try empty, single-item, and duplicate-value inputs.
  2. Print state after every step to observe the algorithm.
  3. Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Run in the Python compiler →

Common mistakes

Recursion without a cache

The same values are recomputed again and again, and fib(40) takes many seconds.

Problem
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)
Fix
@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.

All challenges