# What is memoization?

2 May 2022 (Updated 2 May 2022)

**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

Tagged:
Computing