Course contentsShow
← Python
Lesson 194 of 1,0603. Functions and ModularizationFree lesson

Optimizing Recursive Calls with Memoization

Learners will apply memoization techniques to cache the results of expensive function calls, significantly improving performance in recursive algorithms.

In this lesson, you will learn how to supercharge recursive functions by caching their results using a technique called memoization.

The Efficiency Trap

When you write a recursive function, you often end up solving the same sub-problems over and over again. Consider the classic Fibonacci sequence, where to calculate fib(5), you calculate fib(4) and fib(3). But to get fib(4), you calculate fib(3) and fib(2). Notice that fib(3) is being calculated twice! As the numbers grow, this redundancy turns a fast operation into an incredibly slow one.

Memoization to the Rescue

Memoization is the act of storing the result of a function call in a "cache" (usually a dictionary). Before the function performs its calculation, it first checks: "Have I seen this input before?" If yes, it returns the stored result immediately. If no, it performs the calculation and saves the result for future use.

Here is how you can implement a simple cache using a dictionary:

cache = {}

def fib(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    
    # Store result in cache before returning
    cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]

Why This Works

In our fib function, the cache acts as a shortcut. By using a dictionary, lookups are extremely fast. This transforms an algorithm that might take seconds (or even minutes for larger numbers) to compute into one that finishes almost instantaneously.

By capturing the state of previous results, we stop the recursive "call stack" from ballooning with redundant work. You are essentially teaching your function to learn from its past, ensuring that no calculation is performed more than once.

Key Takeaway: Memoization optimizes recursive algorithms by storing the results of expensive function calls in a cache, preventing redundant computations and drastically reducing execution time.