Start learning free

LESSON 271 OF 348 · MEMOIZATION

Memoization in TypeScript: 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
    Ctrl + Enter to check

    TYPESCRIPT · MEMOIZATION

    Memoization in TypeScript, explained

    What memoization is

    Memoization means remembering the result of a function call so that the next call with the same input can reuse it. The first time the function sees an input, it computes the answer and stores it. Every later call with that input looks the answer up.

    It pays off when a recursive function solves the same subproblem many times. The plain recursive Fibonacci function is the classic case. F(n) is defined as F(n - 1) + F(n - 2), and both calls end up asking for many of the same smaller values.

    Why plain recursion is slow

    Here is the version without any cache:

    function plain(n: number): number {
    return n < 2 ? n : plain(n - 1) + plain(n - 2);
}

    To compute plain(4), the function calls plain(3) and plain(2). The call for 3 calls plain(2) again, and so on. The number of calls roughly multiplies by 1.6 each time n grows by one, which is exponential growth. I counted the calls for n = 30 and the plain version makes 2,692,537 of them, all to return 832040.

    The answer for each k never changes, so computing it more than once is wasted work. With memoization, each value from 2 to n is computed once. The memoized version below makes 59 calls for n = 30.

    The exercise: Fibonacci with a cache

    The task is to write a recursive function that returns F(n), where F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2) for larger n. The constraint is 0 <= n <= 30, and the solution must run in O(n) time with O(n) extra space. For example, F(2) = 1, F(3) = 2 and F(4) = 3.

    The class has a public method fibonacci(n), and the lesson adds a helper method fib(n, cache) that does the recursion.

    Step by step

    1. Declare the helper fib with two parameters: n: number and cache, typed { [key: number]: number }. That type describes an object whose keys are numbers and whose values are numbers. Give cache the default value {}. The default is evaluated each time a call leaves the argument out, so every top-level call starts with an empty cache.
    2. Handle the base case. If n < 2, return n, because F(0) is 0 and F(1) is 1. This also stops the recursion.
    3. Check the cache. !(n in cache) is true when there is no entry for n yet. The parentheses matter: without them the ! would apply to n alone.
    4. Compute and store. Inside the if, set cache[n] to this.fib(n - 1, cache) + this.fib(n - 2, cache). Passing cache along makes every recursive call share the same object. Methods call each other through this.
    5. Return the cached value. After the if, cache[n] is always filled, either by this call or by an earlier one.
    6. Call the helper from fibonacci with return this.fib(n). The second argument is left out on purpose, so the default empty cache is used.

    The solution in TypeScript

    class Solution {
    fib(n: number, cache: { [key: number]: number } = {}): number {
        if (n < 2) {
            return n;
        }
        if (!(n in cache)) {
            cache[n] = this.fib(n - 1, cache) + this.fib(n - 2, cache);
        }
        return cache[n];
    }

    fibonacci(n: number): number {
        return this.fib(n);
    }
}

    To see why it is fast, follow fibonacci(4). The call fib(4) finds nothing in the cache and calls fib(3). That calls fib(2), which calls fib(1) and fib(0), and both return at once. Now cache[2] is 1. Back in fib(3), the second call is fib(1), which returns 1, so cache[3] is 2. Back in fib(4), the second call is fib(2). This time 2 is in the cache, so it returns immediately, and cache[4] becomes 3.

    TypeScript details

    • Index signatures. The type { [key: number]: number } lets you read and write cache[n] for any number n. It describes the shape for the compiler only.
    • Object keys become strings. JavaScript turns every property key into a string, so cache[5] and cache["5"] are the same entry, and 5 in cache and "5" in cache are both true. For this lesson the conversion makes no difference.
    • The in operator checks whether the key exists, even if the stored value is falsy. That matters in general: a cached value of 0 is still a hit. Testing if (!cache[n]) instead would treat a stored 0 as missing and recompute it.
    • Default parameters. A default such as = {} creates a new object on each call that omits the argument. It is not shared between calls, unlike a mutable default in some other languages. Types are erased when TypeScript compiles to JavaScript, but default values are real code, so they still run.
    • Map is an alternative. A Map<number, number> with has, get and set works the same way and keeps the keys as real numbers. The lesson uses a plain object because its type annotation shows the cache's shape clearly.

    Complexity

    Time: O(n). Each value from 2 to n is computed once, with one addition. Every other call to fib returns straight from the base case or the cache. The total number of calls is about 2n.

    Space: O(n). The cache holds at most n - 1 entries, and the recursion goes about n calls deep before the first value is stored. Both are linear.

    Common mistakes

    • Not passing the cache down. If the recursive calls were this.fib(n - 1) without cache, each call would create a new empty cache and the program would behave like the plain version. The one in fibonacci is the only call that should omit it.
    • Forgetting the base case. Without n < 2, the recursion never stops.
    • Writing !n in cache. The ! binds first, so this checks whether false is a key.
    • Testing the cache with truthiness. As noted above, in is the safe check.

    Testing

    • fibonacci(0) gives 0 and fibonacci(1) gives 1.
    • fibonacci(2) gives 1, fibonacci(3) gives 2 and fibonacci(4) gives 3.
    • fibonacci(10) gives 55.
    • fibonacci(30) gives 832040.

    Key takeaways

    • Memoization stores each subproblem's answer the first time and reuses it after that.
    • It turns the exponential recursive Fibonacci into a linear one.
    • The cache must be shared by all the recursive calls, and its entries need a membership check that doesn't rely on truthiness.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free