07 Jun 2023

Memoization

Memoization is a technique that improves the performance of a function by caching its results.

When a memoized function is called with a set of inputs, it checks if it has already computed and stored the result for those inputs. If it has, it returns the cached result instead of recomputing it, saving time and resources.

fib_cache = {}

def fibonacci(n):
    # Check if the result is already cached
    if n in fib_cache:
        return fib_cache[n]

    # Compute and cache the result
    if n <= 1:
        result= n
    else:
        result = fibonacci(n-1) + fibonacci(n-2)

    fib_cache[n] = result
    return result

# The first call will compute and cache the result
print(fibonacci(5))  # Output: 5

# The second call will retrieve the cached result
print(fibonacci(5))  # Output: 5

In this example when the function is called with a specific input (e.g., fibonacci(5)), it first checks if the result is already present in the cache. If it is, it returns the cached result.

Memoization is particularly useful for functions with expensive computations or repetitive calculations. By caching and reusing results, the function can avoid redundant work and achieve a significant performance improvement.