But I also cannot put it inside this function I'm going to define. 'Cause if

you put it inside, we're going to recreate a new table every time we call this

function. Because we do not execute function bodies until we call them. We

need it outside the table, so that it persists, so it's still around from one

call to the next. And it's initially null. Now, we're going to use mutation to update

it appropriately. Really. Okay, so when we want ca, find fibonacci

of x, so we just call x right here, okay? The first thing we're going to do is see,

is it already in the memo table. So, here, I'm using a little library function,

assoc, that takes in something and a list and tells you if that something is in the

list in the following way. Let me show you how this works. You can look it up on your

own in the manual, if you don't get this quickly. So let me define a little list

here. it has to be a list of pairs. Because pairs could have anything you want

in them, but how about just, three different pairs of integers here. Okay.

So that's a little list, xs just looks like this. What assoc does is it takes a

number like 3. And a list of pairs and it checks the car fields of the pairs for

something equal and with the first time it finds one, it returns that pai r. So a

assoc 3 xs returns 3, 4. Assoc 1 xs returns 1, 2 and if it's not in the list,

like 6 you do see a 6 up here but it only looks at the car fields, it returns false.

Meaning I did not find it in the list. So that's assoc. We're going to use assoc up

here, so I had to tell you how it works. So our memo table, which is initially

null, is going to be a list of pairs, and what it's going to be is argument dot

result. We're going to store in that list pairs of, if fibonacci, fibonacci of arg

is result. Alright? So here's what we do. If we find our answer in the table, so we

gotta pair here, and everything that is not false is true, so this works, and

return the cdr of that pair. We looked up the argument x, we found it, return the

result. So that's how we get our reels. In this else branch, we didn't find it. So

now all we have to do is compute it and then put it in the table so people can

find it in the future. So, how do we compute it? That's what this let variable

does, new-ans. We say, well, if x is 1 or 2, then it's 1. Otherwise it's adding

recursive call of x minus 1 and recursive call of x minus 2. Before we return,

change via set! memo to hold a bigger list. Take the old list memo, cons on to

it the pair of our new argument result pair. So that in the future, if anyone

needs fibonacci of x They'll find it in the table. After we've done that, return

this thing that we computed and that is the fibonacci of the number. So, this all

works and what might surprise you is that it's fast. I can ask fibonacci 3 of 1000

and I get this big number. No time at all. So why is this so much efficient than the

naive recursive version, that couldn't even do 40. I don't even think it could do

35. It looks like if it's not in the table, we're still doing these two

recursive calls, and it would blow up exponentially. But we are doing two

recursive calls, whichever one we do second. Will be very, very fast. See, the

problem with exponential blowup is that we make two recursive calls, and they m ake

two recursive calls, and they make two recursive calls, and it blow ups, blows up

2, 4, 8, 16 and 32. But what happens here is we make two recursive calls. The first

recursive call ends up filling up the table with lots of numbers. The second

recursive call ends up finding what it needs in the table. Especially if the

second one is with x minus 2. The second one is x minus 1. It will still have to do

one more recursive call, but then it will find what it needs in the table. And

that's only at the top level. After that, everything's already in the table. So

recursivly, at every step, instead of making two expensive recursive calls, we

make one recursive call. And then, for the next recursive call, everything is already

in the table. So this isn't just twice as fast, it's twice as fast at every level.

And in fact, it's taking something that would take time proportional to 2 to the

x. And turning it to something that takes time proportional to x. Or if you really

want to be picky, since I have to run down this list doing assoc, maybe x squared.

But x squared for a 1000 is nothing. that's no problem at all. Whereas, 2 to

the x, where x is a 1000, is more than I believe, the number of particles in the

universe. So that's our example. It's just a programming idiom. All we did was really

that something that had nothing with fibonacci itself. We created this table.

We always checked it first. If we found it, we did nothing else. Otherwise, we

compute our answer. And before we return, we add our result to the table for the

future. And that is Memoization.