Start learning free

LESSON 265 OF 338 · MEMOIZATION

Memoization in Go: Caching Fibonacci with a Map

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

GO · MEMOIZATION

Memoization in Go, explained

What memoization is

Memoization means remembering the result of a function call so that the same call is never computed twice. The first time the function sees an input, it does the work and stores the answer in a cache. Every later call with that input reads the answer from the cache.

It pays off when a recursive function solves the same subproblem again and again. The classic 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 calls F(n-1) and F(n-2), but F(n-1) calls F(n-2) as well, so that value is computed twice, and the duplication compounds at every level. The number of calls roughly multiplies by 1.6 each time n grows by one. Counting the calls for n = 30 gives 2,692,537, to produce a result of 832,040.

With memoization, each F(k) is computed once. After that, a call for F(k) is a single map lookup. The work drops from exponential to O(n), which is what the lesson's note asks for: O(n) time and O(n) extra space, for 0 <= n <= 30.

The cache in Go: a map

A map[int]int is a natural cache: the key is n and the value is F(n). Three map facts matter here.

A map must be created before writing. make(map[int]int) allocates it. A nil map can be read, and reading gives zero values, but writing to it stops the program with assignment to entry in nil map.
A missing key gives the zero value. Reading m[3] from an empty map returns 0, the same as a stored 0. The two-value form v, ok := m[3] tells them apart: ok is false for a missing key and true for a stored one, even if the stored value is 0.
A map is shared when passed to a function. A map value refers to one underlying table, so a function that receives cache and writes to it is writing to the caller's map. That is why the recursion can pass cache down without a pointer. Slices differ: appending to a slice parameter may not reach the caller.

The exercise: Fibonacci with memoization

The task is to write fibonacci(n int) int as a recursive function with memoization. The lesson splits it in two functions: a public entry point that creates the cache, and a recursive helper fib(n int, cache map[int]int) that uses it.

Declare the helper fib taking n and the cache.
Handle the base cases. For n < 2 the answer is n itself, because F(0) = 0 and F(1) = 1. This also ends the recursion.
Check the cache with _, exists := cache[n] in an if statement's init part, then test !exists. The blank identifier _ discards the value; only the presence matters.
Compute and store. When the key is missing, set cache[n] to fib(n-1, cache) + fib(n-2, cache).
Return cache[n]. After step 4 the key is present, whether it was just computed or found.
In fibonacci, create the map with make(map[int]int) and return fib(n, cache).

func fib(n int, cache map[int]int) int {
    if n < 2 {
        return n
    }
    if _, exists := cache[n]; !exists {
        cache[n] = fib(n-1, cache) + fib(n-2, cache)
    }
    return cache[n]
}

func fibonacci(n int) int {
    cache := make(map[int]int)
    return fib(n, cache)
}

How the cache fills up

For fibonacci(5), the recursion goes down the left side first: fib(5) calls fib(4), which calls fib(3), which calls fib(2). That one reaches the base cases fib(1) and fib(0), stores cache[2] = 1 and returns. Then fib(3) asks for fib(1), a base case, and stores cache[3] = 2. When fib(4) asks for fib(2), it finds the stored value instead of recomputing it. After the call, the map holds map[2:1 3:2 4:3 5:5]. Only keys 2 and above are stored, because smaller values return before the cache is consulted. For n = 30 the cache ends with 29 entries.

Gotchas in Go

Using a zero value as "missing". Writing if cache[n] == 0 to test for absence happens to work for Fibonacci, since no F(n) with n >= 2 is 0, but it fails for any function that can legitimately return 0. The comma-ok form is correct in every case.
Forgetting make. var cache map[int]int declares a nil map, and the first write panics.
Not passing the cache down. If the recursive calls create their own map, nothing is shared and the exponential behaviour returns. Pass the same cache in both calls.
Integer size. int is 64 bits here. F(92) is 7540113804746346429, the largest Fibonacci number that fits. F(93) wraps around silently to a negative number. The lesson stops at n = 30, far from that limit.
Recursion depth. The first call descends n levels before anything is cached. Go grows its stack as needed, so this is no problem for n = 30.

Key takeaways

Memoization stores each subproblem's answer in a cache and reuses it.
It turns recursive Fibonacci from exponential time into O(n) time with O(n) extra space.
In Go, the cache is usually a map created with make and passed to the recursive helper.
Use v, ok := m[key] to tell a missing key from a stored zero.
Base cases come before the cache check, and the cache is checked before the work is done.

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

Start learning free