Start learning free

LESSON 298 OF 414 · MEMOIZATION

Memoization in Rust: Caching Fibonacci with a HashMap

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 7

Guided

Ctrl + Enter to check

RUST · MEMOIZATION

Memoization in Rust, explained

What memoization is

Memoization means remembering the result of a function call so the same call never has to be computed twice. It pays off when a recursive function keeps asking the same questions, which is exactly what the naive recursive Fibonacci does.

The plain version computes F(n) = F(n - 1) + F(n - 2) with two recursive calls. Those calls overlap: F(n - 1) itself needs F(n - 2), so the same values are recomputed again and again. For n = 30 the plain recursion makes 2,692,537 calls to produce 832040. The number of calls grows exponentially with n.

With a cache, each value F(k) is computed once, stored under the key k, and read back on every later request. That leaves about n distinct computations, so the time drops to O(n), with O(n) extra space for the cache and the recursion.

The exercise

The function fibonacci takes n between 0 and 30 and returns F(n), where F(0) = 0, F(1) = 1 and every later value is the sum of the two before it. So fibonacci(2) is 1, fibonacci(3) is 2 and fibonacci(4) is 3. The solution must be recursive and use memoization.

Step by step

Declare a helper fib(n, cache) above fibonacci. The cache is a &mut HashMap<i32, i32>: a mutable borrow lets every recursive call insert into the same map without taking ownership of it.
Handle the base cases. For n < 2 the answer is n itself, since F(0) = 0 and F(1) = 1. This also stops the recursion.
Look in the cache with if let Some(&v) = cache.get(&n) and return the value if it is there.
Compute on a miss: Self::fib(n - 1, cache) + Self::fib(n - 2, cache). Both calls share the same cache.
Store and return. Insert the result under n, then make v the final expression.
Create the cache in fibonacci with let mut cache = HashMap::new(). The key and value types are inferred from the call to fib.
Start the recursion with Self::fib(n, &mut cache) as the final expression.

The solution in Rust

impl Solution {
    fn fib(n: i32, cache: &mut HashMap<i32, i32>) -> i32 {
        if n < 2 {
            return n;
        }
        if let Some(&v) = cache.get(&n) {
            return v;
        }
        let v = Self::fib(n - 1, cache) + Self::fib(n - 2, cache);
        cache.insert(n, v);
        v
    }
    fn fibonacci(n: i32) -> i32 {
        let mut cache = HashMap::new();
        Self::fib(n, &mut cache)
    }
}

The Rust details worth a closer look:

The import. HashMap lives in std::collections. In a program of your own, add use std::collections::HashMap; at the top.
get returns an Option. cache.get(&n) gives Some(&i32) when the key exists and None when it doesn't. The pattern Some(&v) matches the reference and copies the number into v.
Why copying matters. After the if let block the borrow from get is over, so the next lines may use cache mutably. The recursive calls and cache.insert would not be allowed while a reference into the map was still alive.
Passing the cache along. Inside fib the parameter cache is already a &mut HashMap, so the recursive calls pass it by name. Only the first call, in fibonacci, writes &mut cache.
Associated functions. fib takes no self, so it is called as Self::fib from inside the impl block.
Integer size. The values are i32. F(46) = 1836311903 is the largest Fibonacci number that fits, and F(47) is bigger than i32::MAX. With the limit n <= 30 this is never a problem. A u64 would reach much further.

What the cache holds

Base cases are never stored. After fibonacci(10), the cache has 9 entries, one for each key from 2 to 10. Each of those values was computed exactly once. The first call to reach a key does the work. Any later request for that key, such as the second call in F(k) asking for F(k - 2) after F(k - 1) has already computed it, finds it ready.

The recursion is at most n calls deep, because the call for n - 1 runs first and goes all the way down to the base case. That is no problem for the limit of 30.

Common mistakes

Creating the cache inside fib. A new map on every call remembers nothing. The cache must be created once and passed down.
Checking the cache after computing. Looking up the value after the two recursive calls saves no work.
Forgetting to insert. A cache that is only read stays empty, and the function is as slow as the plain version.
Keeping the borrow from get alive. Writing let v = cache.get(&n) and using v after a mutable use of cache is rejected by the borrow checker. Copying the number out with Some(&v) avoids it.
Forgetting mut. let cache = HashMap::new() can't be borrowed with &mut.

Key takeaways

Memoization turns a recursion with overlapping subproblems from exponential time into linear time.
The recipe has three parts: return the cached answer if there is one, otherwise compute it, then store it before returning.
In Rust the cache travels as a &mut HashMap, and the value read from it is copied out before the cache is changed.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free