Memoization (Top-Down DP)

Memoization adds a cache to a recursive state definition. The function still describes the mathematical dependency naturally, but each state body executes only once. Fibonacci is a small example with dramatic overlap: its naive recursion repeatedly recomputes the same indices. We use bounded n so exact long long arithmetic is valid, then discuss why caching does not remove recursion-depth or state-size limitations.

Prerequisites: Introduction to DP; recursion and reference parameters. Related existing lessons: Recursion Fundamentals.

Build the idea

1. Recognize the repeated subproblems

   F(n) calls F(n−1) and F(n−2), whose call trees overlap heavily. For example F(5) needs F(3) both directly through F(4) and through its other branch. The distinct states are only 0…n. This difference between call count and state count is the key recognition step, and it appears in much larger subset, string and game recursions.

2. Define the state

   memo[k] stores F(k), with −1 meaning not computed. Fibonacci values are nonnegative, so this sentinel cannot equal a legitimate answer. The function parameter k is the entire state: the answer does not depend on which caller requested it. A valid answer zero cannot serve as the uncomputed marker unless computed status is stored separately.

3. Derive the transition

   For k≥2, compute fib(k−1)+fib(k−2), store it and return it. Before any recursion, return a cached value if present. The cache lookup turns a repeated dependency into constant work. References to the same vector ensure every branch shares one cache; accidentally passing the vector by value would copy and disconnect the intended stored results.

   $$F\left(k\right)=F(k-1)+F(k-2)$$

4. Base cases and computation order

   F(0)=0 and F(1)=1 are stored as base states when reached. Recursive calls move strictly to smaller indices, so no cycle can wait on itself. Evaluation order is demand-driven: only reachable states are requested, although Fibonacci reaches essentially all of them. The n≤90 contract bounds both recursion depth and numeric growth.

5. Correctness and invariant

   Induct on k: bases match the definition; assuming smaller calls return their true Fibonacci values, their sum is F(k). Caching never changes the returned recurrence value, only whether its body is repeated. There are O(n) distinct cache fills even though the uncached tree is exponential. Recursion still uses O(n) call depth, which would be unsafe for a long million-state dependency chain.

6. Work the example

   For n=5, descend to the bases, then cache F(2)=1, F(3)=2, F(4)=3, F(5)=5. Later requests for an already filled F(2) or F(3) return immediately. The sample asks for F(10)=55; the small cache trace shows the mechanism without requiring the whole call tree.

   k	0	1	2	3	4	5
   cached F(k)	0	1	1	2	3	5

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
long long fib(int n,std::vector<long long>&memo){
    if(memo[n]!=-1){
        return memo[n]; // Cache value and computed status are distinct from a valid zero.
    }
    if(n<2){
        return memo[n]=n;
    }
    return memo[n]=fib(n-1,memo)+fib(n-2,memo);
}
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>memo(n+1,-1);
    std::cout<<fib(n,memo)<<'\n';
}

Complexity analysis

O(n) distinct states with two constant-time transitions each, hence O(n) time. O(n) cache plus O(n) recursive stack. These are fixed-width integer-operation bounds, not arbitrary-precision bit costs.

Example input and output

Read n in 0..90. Print exact F(n), with F(0)=0 and F(1)=1.

Input

10

Output

55

For n=5, descend to the bases, then cache F(2)=1, F(3)=2, F(4)=3, F(5)=5. Later requests for an already filled F(2) or F(3) return immediately. The sample asks for F(10)=55; the small cache trace shows the mechanism without requiring the whole call tree.

Practical applications

Use top-down DP when only a sparse reachable portion of a natural state graph is needed or recursion clarifies transitions. Tabulation avoids recursion overhead and stack depth when a dependency order is easy to enumerate.

Check your understanding

What does caching reduce in Fibonacci?

Put it into practice

Count cache misses and compare them with naive recursive calls for n=20.