There are several steps to making a good sandwich for yourself. You have to get meat, lettuce, mayo, mustard, cheese, jalapeño poppers, and tomatoes out of the fridge. You have to wash the lettuce and cut up the tomatoes. You have to get the bread from wherever you keep your bread and a plate from the cabinet. You have to go out to Chili's and buy the appetizer sampler because it isn't the same when you buy the frozen poppers at the store.

It's a lot of work for one sandwich, but it's worth it when you're hungry and nobody else is begging to make one for you.

Plus: think of the spicy cheese explosion in your mouth. Delicious.

If you had to make dozens of sandwiches, you'd probably want to streamline the process a little more. Think about Chili's itself. They don't go to the fridge for every ingredient on every sandwich. Nope. They have little bins of meat, cheese, tomatoes, jalapeño poppers, and lettuce ready to go. Going to the fridge for a piece of meat, bringing it to the counter, going back to the fridge for a tomato slice, bringing it to the counter, going back again for a cheese slice, bring it back to...you see where this is going.

Chili's line-order cooks have better things to do, like master their fajita sizzling skills.

Instead of heading to the fridge every single time, cooks will chop up a bunch of lettuce and slice up a bunch of tomatoes so it's all ready to go when they need it. You can do the same thing in computers, too, but they call it memoization.

Memoization (not to be confused with memorization) is a way of optimizing code by storing calculated results to reuse later. Compared to recursion, which hides its calculations in a call stack, memoization explicitly stores the data in a structure—like a list or a 2D array—that the code can access as many times as it wants in the program. By memoizing, you can save expensive CPU time, transferring it over into storage space.

It might sound like you're just moving the job from one type of memory to another, and…you are, but you're moving it into a space that's much less expensive to the computer. Any time your recursion has to get really big, save your CPU and memoize the values you get.

You're trying to avoid wasting time spent re-calculating results you already know. For example, suppose your Canadian buddy, a runner, always gives you updates on her most recent races in kilometers, but you're used to miles because…America. You miss half of what she says because you spend so much time trying to calculate the conversions in your head, which is how you missed the fact that the birthday party for her cousin was supposed to be a surprise.

Whoops?

To avoid doing that again, you make a quick conversion list to keep in your wallet (5K equals 3.1 miles, 10K equals 6.2 miles, 25K equals 15.5 miles, and a marathon is 42.2 km, which equals 26.2 miles). That way, the most common distances don't have to be calculated every single time. Don't look now, but you've actually memoized this list of distances.

Bonus: you won't ruin any more surprise parties.

But let's get back to something that feels a little more computer science-y. A classic example? The Fibonacci sequence. In case you just stuffed that math concept in short term memory until the test was over, the Fibonacci sequence is a series of numbers where the next number is found by adding the two numbers before it. You start with 0 and 1 and build from there. The sequence goes like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

If you want to get super math-y, the Fibonacci sequence can be defined like this:

x_n = x_{n – 1} + x_{n – 2},where n is the position in the sequence greater than 0 or 1.

Say you write a program that calculates Fibonacci, finding these numbers:

To get an idea of the value of memoization, let's assume you're at the point of calculating a value for x_{7 ,} You have a recursive algorithm called FIB that has already calculated the Fibonacci value for x₅ and x_6, now all that's left is adding those two numbers together to find x₇. But…the function ended. You'd have to call it again and start all over to get to x₇.

We won't beat around the bush, that's a lot of recursion for no reason.

Since you always want to conserve CPU time, why would you want to calculate x₆ and x₅ again? Instead, just store FIB(x5) and FIB(x6) the first time you calculate those values. That way, finding FIB(x7) is as simple as pulling up those results.

In the dynamic programming solution to the Fibonacci sequence, your code should use a list of size n. It doesn't really matter what type of list you use, but you might want to pick one that can grow easily (we're just throwing that out there). As your algorithm calculates each new Fibonacci number x_n you can store it at index n in the list. Now your recursive routine, instead of calculate all the values between 0 and FIB(n+1), just has to

1. grab FIB(n) and FIB(n-1).
2. sum them.
3. store them in the list at index n+1.

CPU time: saved. You can thank us later.