# Memoization

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

### Perl: Memoized Factorial

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

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)
```