Start learning free

LESSON 270 OF 347 · MEMOIZATION

Memoization in C#: Caching Results with a Dictionary

Lesson O(n) Read the full explanation

In this video lesson we will learn about memoization and use it to improve the recursive fibonacci algorithm written in the previous lesson:

Problem - Fibonacci:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Write a recursive function with memoization that given n, returns F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:
  • 0 <= n <= 30
Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 6
    Ctrl + Enter to check

    C# · MEMOIZATION

    Memoization in C#, explained

    What memoization is

    Memoization means remembering the result of a function call so that the next call with the same arguments can return the stored answer instead of computing it again. It applies to functions that are pure, meaning the same input always gives the same output, and that get called with the same input many times. Recursive functions that split a problem into overlapping subproblems are the classic case.

    The standard example is the Fibonacci sequence, where F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2). The plain recursive version follows the definition directly:

    public int Fib(int n) {
    if (n < 2) {
        return n;
    }
    return Fib(n - 1) + Fib(n - 2);
}

    It is correct and slow. Fib(5) calls Fib(4) and Fib(3), then Fib(4) calls Fib(3) again, and so on. The same values are recomputed over and over, and the number of calls roughly multiplies by 1.6 each time n grows by one. For n = 30, the plain version makes 2,692,537 calls. The time is exponential in n.

    Using a Dictionary as the cache

    A cache needs to map an argument to its answer, and Dictionary<TKey, TValue> (from System.Collections.Generic) does exactly that. For Fibonacci the key is n and the value is F(n), so the type is Dictionary<int, int>.

    The three operations you need are:

    • cache.ContainsKey(n) returns true if an answer for n is already stored.
    • cache[n] = value; stores an answer. If the key is missing, the assignment adds it; if it exists, the assignment replaces the old value.
    • cache[n] reads an answer. If the key is missing, this throws a KeyNotFoundException, so check first or use TryGetValue.

    The pattern is always the same: check the cache, compute and store on a miss, then return the stored value. Every recursive call has to receive the same dictionary, so it is passed along as a parameter.

    The exercise, step by step

    The lesson asks for Fibonacci(int n), with 0 <= n <= 30, running in O(n) time and O(n) extra space. The starting code already creates the dictionary inside Fibonacci.

    1. Write a helper, Fib(int n, Dictionary<int, int> cache), above Fibonacci. The cache has to be a parameter. A default parameter value in C# must be a compile-time constant, and a new dictionary is not one, so Fibonacci creates it and passes it in.
    2. Handle the base case. If n < 2, return n, because F(0) = 0 and F(1) = 1. This also stops the recursion.
    3. Check for a miss with if (!cache.ContainsKey(n)).
    4. Compute and store. Inside the if, set cache[n] to Fib(n - 1, cache) + Fib(n - 2, cache). Each value of n reaches this line at most once.
    5. Return cache[n] after the if. At that point the key is always present, either from an earlier call or from the line you just ran.
    6. Call the helper from Fibonacci with return Fib(n, cache);.
    class Solution {
    public int Fib(int n, Dictionary<int, int> cache) {
        if (n < 2) {
            return n;
        }
        if (!cache.ContainsKey(n)) {
            cache[n] = Fib(n - 1, cache) + Fib(n - 2, cache);
        }
        return cache[n];
    }
    public int Fibonacci(int n) {
        Dictionary<int, int> cache = new Dictionary<int, int>();
        return Fib(n, cache);
    }
}

    Running it, Fibonacci(2) is 1, Fibonacci(3) is 2, Fibonacci(4) is 3 and Fibonacci(30) is 832040.

    Why it is O(n)

    Take Fib(5, cache). It calls Fib(4, cache) first, which calls Fib(3, cache), and so on down to the base cases. As the calls return, F(2), F(3) and F(4) are stored. When Fib(5) then calls Fib(3, cache), the answer is already in the dictionary and it returns immediately.

    Each value from 2 to n is computed once, and each computation does a constant amount of work besides the recursive calls. The total is O(n) time. The dictionary holds up to n - 1 entries, and the recursion goes about n calls deep, so the extra space is O(n).

    Common mistakes

    • Creating the dictionary inside the recursive method. Each call would get a fresh, empty cache and nothing would ever be reused. The cache must be created once and shared.
    • Reading before storing. return cache[n]; without the check throws KeyNotFoundException for any n not yet stored.
    • Calling the cached method with the wrong arguments. Inside Fib, the recursive calls must be Fib(n - 1, cache), not Fib(n - 1). The two-argument signature is the only one that exists.
    • Memoizing impure functions. If the result depends on something other than the arguments, such as the current time or a changing field, a stored answer can be wrong later.
    • Overflow for large inputs. This lesson stops at n = 30. In an int, the sequence overflows after F(46), and by default C# wraps the result silently instead of reporting an error.

    Key takeaways

    • Memoization stores a function's results by argument, so repeated calls cost a lookup.
    • A Dictionary<int, int> passed through every recursive call is the usual cache in C#.
    • Check with ContainsKey before reading, because the indexer throws on a missing key.
    • Memoizing Fibonacci turns exponential time into O(n) time with O(n) extra space.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free