What is memoization? | Sajad Torkamani

On this page

Memorization is an optimization technique in programming in which you store the results of expensive function calls and return cached results when functions are re-invoked with the same inputs. This way, you avoid redoing expensive computations.

Memoization only works for pure functions that always return the same result when given the same input.

Here’s a pseudocode example of how a factorial function can be memoized:

Non-memoized version

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else
        return factorial(n – 1) times n [recursively invoke factorial 
                                        with the parameter 1 less than n]
    end if
end function

Memoized version

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else if n is in lookup-table then
        return lookup-table-value-for-n
    else
        let x = factorial(n – 1) times n [recursively invoke factorial
                                         with the parameter 1 less than n]
        store x in lookup-table in the nth slot [remember the result of n! for later]
        return x
    end if
end function

Sources

Memoization – Wikipedia

Tagged: Computing

Non-memoized version

Memoized version

Sources

Leave a comment Cancel reply