Memoization: Storing Solutions to Avoid Re-computation

Imagine you're navigating a complex maze, and you find yourself at a junction you've encountered before. Instead of figuring out the best path from that junction all over again, wouldn't it be incredibly helpful to have a little notepad where you've jotted down the optimal route you discovered last time? This, in essence, is the core idea behind memoization in computer science. It's a powerful technique used within dynamic programming to significantly speed up algorithms by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Let's consider a classic example: calculating Fibonacci numbers. The Fibonacci sequence is defined as F(n) = F(n-1) + F(n-2), with base cases F(0) = 0 and F(1) = 1. A straightforward recursive implementation would look something like this:

While this is mathematically elegant, it's computationally inefficient. Notice how fibonacci(3) would be calculated multiple times when computing fibonacci(5). fibonacci(5) calls fibonacci(4) and fibonacci(3). fibonacci(4) calls fibonacci(3) and fibonacci(2). See the repeated calculation of fibonacci(3)? This redundancy grows exponentially as 'n' increases, leading to a very slow algorithm for larger inputs.

graph TD
    A[fib(5)] --> B[fib(4)]
    A --> C[fib(3)]
    B --> D[fib(3)]
    B --> E[fib(2)]
    C --> F[fib(2)]
    C --> G[fib(1)]
    D --> H[fib(2)]
    D --> I[fib(1)]
    E --> J[fib(1)]
    E --> K[fib(0)]
    F --> L[fib(1)]
    F --> M[fib(0)]

This is where memoization comes to the rescue. We can introduce a cache (often a map or an array) to store the results of our fibonacci calls. Before computing fibonacci(n), we first check if the result for n is already in our cache. If it is, we simply return the cached value. Otherwise, we compute it, store it in the cache, and then return it.