Optimizing Fibonacci with Memoization

In our last lesson, we confronted the dramatic inefficiency of a naive recursive solution for the Fibonacci sequence. By visualizing the recursion tree and analyzing the time complexity, we proved that its $O (2^{n})$ runtime, caused by repeatedly solving the same overlapping subproblems, makes it impractical.

Today, we will introduce the cure for this ailment: memoization. This technique is our first foray into the world of Dynamic Programming and directly tackles the problem of overlapping subproblems. Our objective is to apply memoization to our recursive Fibonacci solution, transforming its complexity from exponential to linear. This "top-down" DP approach is elegant because it allows us to optimize the code while preserving its original recursive logic.

The Idea: Remember, Don't Recompute

The core problem, as we saw, is redundant work. When calculating fib(6), the recursive calls end up calculating fib(3) three times, fib(2) five times, and so on.

The recursion tree for `fib(6)`. The black arrows show the first time a subproblem is encountered. The grayed-out subtrees represent redundant computations for values that have already been calculated in the black-arrow path.

Memoization is based on a simple, powerful idea: if you've already solved a problem, don't solve it again. Instead, write down the answer somewhere. The next time you're asked, just look up the answer. In programming, this "somewhere" is a cache, often an array or a hash map, and the process is called memoization (from "memo," as in writing a note to yourself).

For the Fibonacci sequence, this means that the first time we compute fib(n), we store its result. Any subsequent time our code needs fib(n), it retrieves the stored value in constant time instead of launching into another expensive recursive cascade.

The following video from Abdul Bari provides an excellent visualization of this process. He traces the execution on the recursion tree, showing exactly which branches are "pruned" or skipped thanks to memoization.

4 Principle of Optimality - Dynamic Programming introduction

This video masterfully illustrates the effect of memoization.

Watch the segment from observing the redundancy to the final count of calls. Pay close attention to how he uses an auxiliary array to keep track of computed values and avoids re-entering recursive branches. Notice the dramatic reduction in the number of function calls.

Implementing Memoization: The Three Key Steps

Translating the idea of memoization into code involves making three small but crucial changes to our original recursive function. We will use an array, which we'll call dp, to store the results of our subproblems. Since you're using C++, a std::vector<int> is a perfect tool for this.

The takeuforward tutorial provides a clear, step-by-step guide to this process.

Dynamic Programming Introduction - Tutorial

This article clearly defines the three steps needed to memoize any recursive solution.

Please read the section titled Part - 1: Memoization. Focus on understanding the three outlined steps, as they form a general pattern for converting a recursive solution into a top-down DP solution.

Let's formalize those three steps for our C++ Fibonacci function:

Create a DP array/vector: We'll declare a vector<int> dp of size n + 1. We must initialize it with a special value to signify that a subproblem has not yet been computed. A common choice is -1, as Fibonacci numbers are non-negative.
Check the DP array: At the very beginning of our recursive function, right after the base cases, we add a new check: if (dp[n] != -1). If this condition is true, it means we have computed this value before. We simply return dp[n], avoiding any further recursion for this branch.
Store the result: If the value was not found in our dp array, we proceed with the recursive calculation as before: fib(n - 1) + fib(n - 2). However, just before we return this newly computed value, we store it in our table for future use: dp[n] = result.

Here is what the C++ implementation looks like, putting all three steps together.

Dynamic Programming Introduction - Tutorial

This section provides the complete C++ code for the memoized solution.

Examine the C++ code block provided in the article. You can find it under the Code heading. Notice how the three steps are integrated into the fib function: The dp vector is passed by reference. The if (dp[n] != -1) check is added near the top. The result of the recursive calls is stored in dp[n] before being returned.

To see this code in action and get another excellent walkthrough of the logic, the "take U forward" video is a perfect companion to the article you just read.

DP 1. Introduction to Dynamic Programming | Memoization | Tabulation | Space Optimization Techniques

This video by "take U forward" explains the concepts of overlapping subproblems and memoization visually and in code.

First, watch the recursion tree segment to see the identification of overlapping subproblems. Then, watch from the introduction of memoization to the three-step implementation process. The presenter methodically explains how to convert the recursive code into its memoized version.

Analyzing the Memoized Solution

We have transformed the algorithm. But what is the concrete impact on performance? Since you value formal proofs, let's analyze the time and space complexity.

Time Complexity

In the memoized version, each subproblem fib(k) (for k from 0 to n) is computed at most once.

The first time fib(k) is called, the check dp[k] != -1 fails. The function then executes its main logic (two recursive calls and one addition) and stores the result. This takes some constant amount of work, let's call it $c$ , plus the time for the recursive calls.
Every subsequent time fib(k) is called, the check dp[k] != -1 succeeds. The function immediately returns the stored value. This is an $O (1)$ operation.

The recursion tree is effectively "pruned." A call fib(k) will only recurse if k has not been seen before. Because there are $n + 1$ distinct states (from 0 to n), our function will perform the full computation for each state only once.

Therefore, the total time complexity is the sum of the work for each state: $(n + 1) \times O (1) = O (n)$ . We have successfully reduced the complexity from exponential $O (2^{n})$ to linear $O (n)$ .

The cp-algorithms article makes this point powerfully by comparing the number of function calls before and after memoization.

Introduction to Dynamic Programming

This article provides a concise analysis of the performance gain from memoization.

Read the section Speeding up with Memoization. The comparison for f(29)—from over a million calls to just 57—is a striking illustration of the power of this technique. The article also provides alternative C++ implementations, including one using unordered_map, which is useful if your subproblem states are not contiguous integers.

Space Complexity

The analysis of space requires considering two components:

Recursion Stack Space: The recursive calls create a call stack. In the memoized version, the deepest the recursion will go is the path fib(n) -> fib(n-1) -> ... -> fib(1). This has a depth of $n$ , so the stack space is $O (n)$ .
DP Array Space: We allocate an array (or vector) of size n + 1 to store the results of our subproblems. This requires $O (n)$ space.

Combining these, the total space complexity is $O (n) + O (n)$ , which simplifies to $O (n)$ . This is an increase from the $O (n)$ stack space of the naive recursive solution, but it is a small price to pay for the colossal improvement in time complexity.

Conclusion

In this lesson, you have learned your first, and arguably most intuitive, dynamic programming technique. By simply storing the results of subproblems, we transformed a non-viable exponential algorithm into an efficient linear-time solution, all while keeping the readable, top-down recursive structure.

Key Takeaways:

Memoization is a top-down Dynamic Programming technique that optimizes recursive algorithms by caching the results of subproblems.
It is perfectly suited for problems with the overlapping subproblems property.
The implementation involves a simple three-step pattern: create a cache, check the cache at the start of the function, and store the result in the cache before returning.
Applying memoization to the Fibonacci problem reduces its time complexity from $O (2^{n})$ to $O (n)$ at the cost of $O (n)$ additional space for the cache.

You now understand how to solve problems from the "top-down." In the next lesson, we'll explore the second major DP approach: tabulation. We will solve the same Fibonacci problem from the "bottom-up," starting from the base cases and iteratively building our solution without any recursion.