Memoization facts for kids

In computing, memoization is a smart trick used to make computer programs run faster. It works by "remembering" the results of calculations that take a long time. If the program needs the same calculation again, it just uses the remembered answer instead of doing the work all over. This is a type of caching, which means storing data so it can be found quickly later.

What Does "Memoization" Mean?

The word memoization was created by a computer scientist named Donald Michie in 1968. It comes from the Latin word memorandum, which means 'to be remembered'. Think of it like writing a quick "memo" to yourself to remember something important. So, memoization means turning the results of a calculation into something that can be easily remembered and used again. Even though it sounds a bit like memorization, it has a special meaning in the world of computers.

How Memoization Works

A function that uses memoization "remembers" the answers for certain inputs. Imagine you have a math problem: `2 + 2`. If you solve it once and get `4`, you don't need to solve it again every time someone asks `2 + 2`. You just remember the answer is `4`.

That's what memoization does for computer programs. When a program calls a function with specific inputs, it stores the result. If the function is called again with the *exact same inputs*, it doesn't do the calculation again. Instead, it quickly gives back the stored answer. This saves a lot of time, especially for complex calculations.

For memoization to work, a function must always give the same answer for the same inputs. This is like `2 + 2` always being `4`. If a function's answer could change (for example, if it depended on the time of day), memoization wouldn't be useful.

Speed vs. Memory

Memoization makes programs faster, but it uses more computer memory to store all those remembered results. This is a common choice in computing called a "space-time tradeoff." It means you trade some memory space for faster processing time.

Think of it like this:

• Time cost: How long a program takes to finish a task.
• Space cost: How much memory a program uses.

Memoization helps reduce the time cost by increasing the space cost.

An Example: Factorial

Let's look at an example using something called a "factorial." The factorial of a number (like 5!) means multiplying that number by all the whole numbers smaller than it down to 1. So, 5! = 5 × 4 × 3 × 2 × 1 = 120.

Here's how a computer might calculate a factorial without memoization:

• To find 5!, it calculates 4! first, then multiplies by 5.
• To find 4!, it calculates 3! first, then multiplies by 4.
• And so on, until it gets to 0! (which is 1).

This means to find 5!, the computer has to do calculations for 5!, 4!, 3!, 2!, 1!, and 0!.

Now, with memoization:

• When the computer calculates 5!, it also calculates and stores the results for 4!, 3!, 2!, 1!, and 0!.
• If you later ask for 3!, the computer already has the answer stored. It doesn't need to do any new calculations!
• If you ask for 7!, the computer only needs to calculate 7! and 6!. It already has 5! (and all smaller factorials) stored from before.

This way, the more you ask for factorials, the faster the computer gets at giving you the answers because it remembers more and more results.

Other Ways Memoization Is Used

Automatic Memoization

Sometimes, programmers add memoization to their code themselves. But in some programming languages, computers can even add memoization automatically! This means the computer can figure out which functions can benefit from remembering results and set up the "memory" system on its own. It's like the computer learning to take notes for itself to work more efficiently.

Helping Parsers Understand Language

Memoization is also very useful in programs called "parsers." Parsers are like the grammar experts of computers. They help programs understand human language or programming code.

Imagine a parser trying to understand a complicated sentence. It might try different ways to read the sentence. If it tries one way and fails, it might have to go back and try another. This "going back" often means re-doing parts of the work it already did.

With memoization, the parser can remember the results of its attempts to understand parts of the sentence. If it tries to understand the same part again (even if it's trying a different overall way to read the sentence), it can just use the remembered result. This saves a lot of time and makes the parser much faster at figuring things out, especially for complex or confusing sentences.

See also

• Computational complexity theory – Learn more about how we measure how fast and how much memory programs use.
• Lazy evaluation – Another way computers can save work by only doing calculations when they are absolutely needed.
• Materialized view – A similar idea used in databases to store results of common questions.