Start learning free

LESSON 295 OF 414 · MEMOIZATION

Memoization in Scala: Caching Recursive Fibonacci

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

Guided

Ctrl + Enter to check

SCALA · MEMOIZATION

Memoization in Scala, explained

What memoization is

Memoization means remembering the answer to a function call the first time you compute it, and returning the remembered answer whenever the same call comes up again. It applies to functions where the same arguments are requested many times and the answer depends only on the arguments. Recursive functions that split a problem into overlapping subproblems are the classic case.

The Fibonacci numbers show the problem clearly. They are defined by F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2). The direct recursive translation is a single line:

def fibPlain(n: Int): Int =
    if (n < 2) n else fibPlain(n - 1) + fibPlain(n - 2)

It is correct but slow. Computing F(5) calls F(4) and F(3), and F(4) calls F(3) again, so the same work repeats down the tree. The number of calls grows exponentially: fibPlain(30) makes 2,692,537 calls to produce 832040.

The idea: a cache shared by every call

Keep a map from n to F(n). Before computing a value, check the map. If the answer is there, return it. If not, compute it, store it, and return it. Each distinct n is then computed once, and every other request is a lookup. With memoization, the same fib(30) needs only 59 calls.

The cache must be shared by all the recursive calls, so it is created once in the outer method and passed down as a parameter. A cache created inside the recursive function would be empty on every call and save nothing.

The exercise: fibonacci with a cache

The task is to write fibonacci(n), returning F(n) for 0 <= n <= 30 with a recursive function and memoization, in O(n) time and O(n) extra space. The starting code already creates the cache in fibonacci:

val cache = mutable.Map[Int, Int]()

Step by step

Declare the helper fib(n: Int, cache: mutable.Map[Int, Int]): Int above fibonacci. It takes the cache as a parameter so every call shares one map.
Handle the base case. For n < 2, return n itself, since F(0) = 0 and F(1) = 1. This also stops the recursion.
Check the cache with !cache.contains(n).
Compute and store. When the key is missing, set cache(n) to fib(n - 1, cache) + fib(n - 2, cache).
Return cache(n). After the if, the key is always present.
Call the helper from fibonacci with the cache that is already declared there.

The solution in Scala

class Solution {
    def fib(n: Int, cache: mutable.Map[Int, Int]): Int = {
        if (n < 2) {
            return n
        }
        if (!cache.contains(n)) {
            cache(n) = fib(n - 1, cache) + fib(n - 2, cache)
        }
        return cache(n)
    }
    def fibonacci(n: Int): Int = {
        val cache = mutable.Map[Int, Int]()
        return fib(n, cache)
    }
}

Calling fibonacci(10) returns 55 after 19 calls to fib, and fibonacci(30) returns 832040 after 59.

Scala details

Mutable versus immutable maps. Scala's default Map is immutable, so it can't be updated in place. A memo table needs scala.collection.mutable.Map, which is what mutable.Map refers to here.
Indexing and updating use parentheses. cache(n) reads a value, and cache(n) = value is shorthand for calling the map's update method.
Reading a missing key throws. cache(6) on a map without key 6 throws java.util.NoSuchElementException: key not found: 6. That is safe in this solution because the value is stored before it is read. To look up without risk, cache.get(6) returns an Option (None here) and cache.getOrElse(6, -1) returns a default.
Explicit return. The lesson writes return for clarity. In idiomatic Scala the last expression of a block is its value, so the final line could be just cache(n).
Int is 32 bits. F(30) is 832040, far below the limit of about 2.1 billion. F(46) is the last Fibonacci number that fits in an Int, which is why the lesson caps n at 30; larger values would need Long or BigInt.

Complexity

Time: O(n). Each value from 2 to n is computed once. Every further call that asks for it finds it in the map. mutable.Map is a hash map, so a lookup or insertion takes constant time on average.

Space: O(n). The map holds at most n - 1 entries, and the recursion goes about n calls deep before the first value is stored, so the call stack is O(n) too.

Common mistakes

Creating the cache inside fib. Each call would get its own empty map, and the running time would stay exponential.
Caching the base cases. It isn't wrong, but it isn't needed: returning n directly is just as fast.
Using the immutable Map. Map[Int, Int]() without the mutable prefix has no update, so cache(n) = ... doesn't compile.
Forgetting to pass the cache in the recursive calls, which gives the same repeated work as plain recursion.

Key takeaways

Memoization trades memory for time: store each answer once, then look it up.
The cache must be shared by every recursive call, so pass it as a parameter.
In Scala, use mutable.Map for the cache, and contains before reading with cache(key).
Memoizing Fibonacci reduces millions of calls to a few dozen: from exponential time to O(n).

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

Start learning free