Start learning free

LESSON 296 OF 415 · MEMOIZATION

Memoization in Swift: Fibonacci with a Dictionary Cache

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

    SWIFT · MEMOIZATION

    Memoization in Swift, explained

    What memoization is

    Memoization means remembering the answer to a function call, so the next call with the same argument returns the stored answer instead of computing it again. It pays off when a recursive function keeps solving the same smaller problems.

    The Fibonacci numbers are the standard example. They are defined by F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2). A plain recursive version looks natural, but F(n - 1) and F(n - 2) both need many of the same smaller values, and the work repeats. In Swift, a plain recursive fib(30) makes 2,692,537 calls to produce 832,040. With memoization it makes 59 calls. The task is to write a recursive function with memoization that runs in O(n) time and uses O(n) extra space, for 0 <= n <= 30.

    How the cache works

    The cache is a dictionary from n to F(n), of type [Int: Int]. Before computing F(n), the function looks in the cache. If the answer is there, it returns it. If not, it computes it from F(n - 1) and F(n - 2), stores it, and returns it. Each value from 2 to n is computed once, so the total work is proportional to n.

    The cache has to be shared by every recursive call. In Swift that takes one extra idea, because a dictionary is a value type.

    Why inout

    Arrays, dictionaries and strings in Swift are values: passing one to a function gives that function its own copy, and changes inside it are invisible to the caller. A plain parameter is also a constant inside the function. If fib took the cache as an ordinary parameter, it could not store anything into it, and a mutable local copy would be thrown away on return.

    Marking the parameter inout fixes this. The function can change the argument, and the changes are copied back to the caller's variable when the function returns. The caller passes it with an ampersand: fib(n - 1, &cache). Because the argument has to be a variable that can change, the variable is declared with var, not let.

    Step by step

    1. Declare the helper fib(_ n: Int, _ cache: inout [Int: Int]) -> Int above fibonacci, with cache as inout so that every recursive call writes into the same dictionary.
    2. Handle the base case. If n < 2, return n: F(0) is 0 and F(1) is 1. This also ends the recursion.
    3. Check for a missing entry with cache[n] == nil. A dictionary subscript returns an optional, which is nil when the key is absent.
    4. Compute and store. Inside the if, set cache[n] to fib(n - 1, &cache) + fib(n - 2, &cache).
    5. Return the stored value with cache[n]!. The ! unwraps the optional, which is safe because the entry exists by this point: either it was already there or the if just stored it.
    6. Start it from fibonacci. The starter code already declares var cache = [Int: Int](). Return fib(n, &cache).

    The solution in Swift

    class Solution {
    func fib(_ n: Int, _ cache: inout [Int: Int]) -> Int {
        if n < 2 {
            return n
        }
        if cache[n] == nil {
            cache[n] = fib(n - 1, &cache) + fib(n - 2, &cache)
        }
        return cache[n]!
    }
    func fibonacci(_ n: Int) -> Int {
        var cache = [Int: Int]()
        return fib(n, &cache)
    }
}

    Swift details worth a closer look:

    • Dictionary lookups are optional. cache[n] has the type Int?. Comparing it with nil asks "is the key missing?". Assigning to cache[n] inserts or replaces the entry; assigning nil would remove it.
    • The base cases are never cached. The function returns early for n < 2, so the dictionary only holds values for 2 and up. For fibonacci(30) it ends with 29 entries, for the keys 2 to 30.
    • One &cache per call. Every use of an inout argument needs the ampersand, so both recursive calls in the sum have it. Passing the same variable twice in one call is not allowed, but two separate calls added together are fine.
    • The force unwrap. cache[n]! crashes if the entry is missing. Here that can't happen, because the line above guarantees it. An alternative that avoids ! is if let cached = cache[n] { return cached } at the start, then computing and storing the value.
    • Overflow. Int is 64 bits in Swift, and arithmetic overflow crashes the program instead of wrapping. With n <= 30 this is no concern, since F(30) is 832,040. The 64-bit limit would be reached around F(93).

    Complexity

    Time: O(n). The first call for each k from 2 to n does the real work, which is one addition and two calls that find cached answers or are the base cases. Dictionary lookups take constant time on average. That makes about 2n calls in total, and for n = 30 exactly 59.

    Space: O(n). The dictionary holds up to n - 1 entries, and the recursion reaches a depth of about n before the first answers come back. Both are linear.

    Common mistakes

    • Leaving out inout. Without it, the compiler rejects cache[n] = ... because a parameter is a constant. Fixing that with a local var copy compiles, but each call then fills its own copy, nothing is shared, and the speed-up is lost.
    • Forgetting the &. Calling fib(n - 1, cache) for an inout parameter is a compile error.
    • Declaring cache with let. An inout argument must be mutable, so let is rejected.
    • Caching after the recursion instead of storing the result. The check, the store and the final lookup all matter: skipping the store makes every call recompute.
    • Putting the cache in the wrong scope. If fibonacci created a fresh dictionary inside fib on every call, nothing would be reused. The cache must be created once, in fibonacci, and passed down.

    Testing

    • n = 0 gives 0, and n = 1 gives 1.
    • n = 2 gives 1, n = 3 gives 2 and n = 4 gives 3.
    • n = 30 gives 832040.

    Key takeaways

    • Memoization stores each answer the first time it is computed, and looks it up afterwards.
    • In Swift, a dictionary is a value, so a cache shared by recursive calls is passed as an inout parameter with &.
    • A dictionary lookup returns an optional: compare with nil to test for a missing key.
    • The cache turns exponential recursion into O(n) time and space.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free