Boost Recursive Algorithms with Memoization: A Practical Guide

Memoization is described by Wikipedia as a technique originally created to speed up computer programs by storing function results and returning them when the same arguments appear, especially useful in recursive functions.

The term was coined by Donald Michie in 1968, derived from the Latin "memorandum".

Memoization implements dynamic programming to make recursive algorithms efficient without major changes to the natural recursive form.

Basic Idea

First design a natural recursive algorithm.

If recursive calls with identical parameters occur repeatedly, store the solutions of these sub‑problems in a table to avoid recomputation.

Implementation

To memoize a recursive algorithm, maintain a table (array or object) of sub‑problem solutions. Each entry is initialized with a sentinel value (e.g., -1) indicating it has not been computed. When a sub‑problem is first encountered, compute its solution and store it; subsequent calls retrieve the cached value.

Example: computing the n‑th Fibonacci number.

static int fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n - 1) + fib(n - 2);
}

The above runs in O(2ⁿ) time, as illustrated by the following diagram.

By caching results, the algorithm reduces to O(n):

static int fibonacciMemo(int n) {
    int[] fibs = new int[n + 1];
    Arrays.fill(fibs, -1);
    return fib(n, fibs);
}
static int fib(int n, int[] fibs) {
    if (n == 0 || n == 1) return n;
    if (fibs[n] == -1) {
        fibs[n] = fib(n - 1, fibs) + fib(n - 2, fibs);
    }
    return fibs[n];
}

With a single small modification, the recursive algorithm runs in linear time.

Advantages

The algorithm does not need to be converted to an iterative form and often provides efficiency comparable to (or better than) traditional dynamic programming.

On an i7 Octa‑core machine, computing the 45th Fibonacci number without memoization takes about 5136 ms, while the memoized version completes in essentially 0 ms.

All source code referenced is available on GitHub.