Memoization is an optimization technique which avoids recalculation by an algorithm of a previously processed input. This is achieved by creating a look-up table which links previous inputs to their corresponding return values. When the algorithm is passed a parameter found to be in the look-up table, its previously calculated output is immediately returned; otherwise, the input and its output are calculated and stored together in the look-up table.

Memoization is often best applied to intensive, repetitive algorithms. The downside to memoization is that it memory is consumed for storing the look-up table. In most cases this will not be an issue, with memory consumption often being negligible and well worth the significant increase in speed.

Implementations[edit]

Perl: Memoized Factorial[edit]

In this example, with factorial() initially being called with 24, the factorials of 24 and its lower numbers are calculated and saved to the look-up table. If factorial() is called with 24 or less again in this program, the result can immediately be identified from the look-up table and returned without having to calculate it again.

my %table;
$table{0} = 1; # Manually linking input '0' to output '1' in the look-up table.

sub factorial {
    my $number = shift;
    my $factorial;

    if ( exists $table{$number} ) {
        return $table{$number}; # Input found in the look-up table, returning stored value.
    }
     else {
        $factorial = factorial($number - 1) * $number;
    }

    $table{$number} = $factorial; # Inserting newly calculated value into new table.

    return $factorial;
}

factorial(24);

Python: Memoized Factorial[edit]

In this example, with factorial() initially being called with 24, the factorials of 24 and its lower numbers are calculated and saved to the look-up table. If factorial() is called with 24 or less again in this program, the result can immediately be identified from the look-up table and returned without having to calculate it again.

table = {0: 1} # Manually linking input '0' to output '1' in the look-up table.

def factorial(number):
    if number in table:
        return table[number] # Input found in the look-up table, returning stored value.
    else:
        result = factorial(number - 1) * number
        table[number] = result # Inserting newly calculated value into new table.
        return result

factorial(24)