The computer science students I tutor are learning memoization using the classic example of recursive Fibonacci. I remember learning these same topics during my data structures and algorithms courses. I also remember being very surprised at the performance before and after memoization.

Recursive Fibonacci in C#

Generating the Fibonacci sequence in a C# Console Application can look like this.

using System;

namespace Fibonacci
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 0; i < 51; i++)
            {
                Console.WriteLine($"Fib({i}) = {Fib(i)}");
            }
        }

        static long Fib(int n)
        {
            if (n < 2) return n;

            return Fib(n - 1) + Fib(n - 2);
        }
    }
}

There are more terse ways to write it, but this C# application will generate the Fibonacci sequence from 0 to 50. It's pretty quick until I get to around Fib(43) on my laptop, but then it starts to slow up quite noticeably. We can dramatically increase the performance by adding memoization.

Memoization

Memoization is a term that describes a specialized form of caching related to caching output values of a deterministic function based on its input values. The key here is a deterministic function, which is a function that will return the same output based on a given input. This is true of the Fibonacci function shown above. It will always return the same output based on the input.

Since we know the Fibonaaci function is a deterministic function, we can cache the return value for each given input. At the beginning of the function we can check the cache to see if we had run the calculations earlier. If so, we can return the value from the cache as opposed to re-running the calculation again.

In this case let's use a Dictionary in C# as the cache. The input parameter to the function, n, will serve as the key to the Dictionary (cache), and of course, the return value will serve as the value associated with that key.

We can re-write the C# Console Application using memoization as such.

using System;
using System.Collections.Generic;

namespace Fibonacci
{
    class Program
    {
        static Dictionary<int, long> _memo = 
            new() { { 0, 0 }, { 1, 1 } };

        static void Main(string[] args)
        {
            for (int i = 0; i < 51; i++)
            {
                Console.WriteLine($"Fib({i}) = {Fib(i)}");
            }
        }

        static long Fib(int n)
        {
            if (_memo.ContainsKey(n))
                return _memo[n];

            var value = Fib(n - 1) + Fib(n - 2);

            _memo[n] = value;

            return value;
        }
    }
}

The function now checks to see if it has already calculated a value in the past for the given input, and if so, returns the value from the Dictionary, avoiding the calculation again. If this is the first time it has calculated a value for the given input, it performs the calculation. However, before returning the value, it caches the value in the Dictionary so as not to calculate the same value in the future.

If you now run this new code using memoization, you will see it's much faster at larger values of n.

As a side note, I removed the original base case of checking for n < 2 by pre-populating the Dictionary with those values. In this situation, returning the value from the Dictionary is our base case for ending recursion.

Wrap Up

It's worthwhile to understand the nature of recursive Fibonacci and the concept of memoization, because they are often used together to illustrate the usefulness of memoization. It's also a popular technical interview question for computer science students.

I didn't mention it earlier, but memoization is used mainly for functions that have long running times, e.g. expensive calls. If it's very simple and quick in terms of both space and time complexity to call a function over and over, there isn't any real reason to use memoization. Although memoization dramatically improves the speed of recursive Fibonacci, there are other algorithms for calculating the Fibonacci sequence that don't benefit from memoization.

And one final point worth noting is that one often uses memoization as a wrapper (decorator) around functions, particularly non-recursive functions. In those cases, you don't modify the function to use memoization, but decorate or wrap the function with another function that only contains the memoization functionality. In this way you stick to important design principles and patterns like the Single Responsibility Principle and Decorator Pattern.