Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu.

PROFESSOR: OK. I want to start where we left off. You remember last time we were looking at Fibonacci. And so we've got it up here, a nice little recursive implementation of it. And the thing I wanted to point out is, we've got this global variable number of calls. Which is there not because Fibonacci needs it but just for pedagogical reasons, so that we can keep track of how much work this thing is doing. And I've turned on a print statement which was off last time. So we can see what it's doing is it runs. So let's try it here with Fib of 6.

So, as we would hope, Fib of 6 happens to be 8. That right? That right, everybody? Should Fib of 6 be 8? I don't think so. So first thing we should do is scratch our heads and see what's going on here. Alright, let's look at it. What's happening here? This is your morning wake-up call. What is happening? Yes.

STUDENT: [INAUDIBLE]

PROFESSOR: See if I can get it all the way to the back. No I can't. That's embarrassing. Alright. So if n is less than or equal to 1, return n. Well that's not right, right? What should I be doing there? Because Fib of is? What? 1. So let's fix it. How about that, right? Or maybe, what would be even simpler than that? Maybe I should just do that.

Now let's try it. We feel better about this? We like that answer? Yes, no? What's the answer, guys? What should Fibonacci of 6 be? I think that's the right answer, right? OK.

So what do I want you to notice about this? I've computed a value which is 13. And it's taken me 25 calls. 25 recursive calls to get there. Why is it taking so many? Well, what we can see here is that I'm computing the same value over and over again. Because if we look at the recursive structure of the program, what we'll see that's going on here is, I call Fib of 5 and 4, but then Fib of 5 is also going to call Fib of 4. So I'm going to be computing it on those branches. And then it gets worse and worse as I go down.

So if I think about computing Fib of I'm going to be computing that a lot of times. Now, fortunately, Fib of 0 is short. But the other ones are not so short. And so what I see is that as I run this, I'm doing a lot of redundant computation. Computing values whose answer I should already know. That's, you'll remember last time, I talked about the notion of overlapping sub-problems. And that's what we have here. As with many recursive algorithms, I solve a bigger problem by solving a smaller instance of the original problem. But here there's overlap. The instant unlike binary search, where each instance was separate, here the instances overlap. They share something in common. In fact, they share quite a lot in common. That's not unusual.

That will lead me to use a technique I mentioned again last time, called memoization. Effectively, what that says is, we record a value the first time it's computed, then look it up the subsequent times we need it.

So it makes sense. If I know I'm going to need something over and over again, I squirrel it away somewhere and then get it back when I need it. So let's look at an example of that.

So I'm going to have something called fast Fib.

PROFESSOR: OK. I want to start where we left off. You remember last time we were looking at Fibonacci. And so we've got it up here, a nice little recursive implementation of it. And the thing I wanted to point out is, we've got this global variable number of calls. Which is there not because Fibonacci needs it but just for pedagogical reasons, so that we can keep track of how much work this thing is doing. And I've turned on a print statement which was off last time. So we can see what it's doing is it runs. So let's try it here with Fib of 6.

So, as we would hope, Fib of 6 happens to be 8. That right? That right, everybody? Should Fib of 6 be 8? I don't think so. So first thing we should do is scratch our heads and see what's going on here. Alright, let's look at it. What's happening here? This is your morning wake-up call. What is happening? Yes.

STUDENT: [INAUDIBLE]

PROFESSOR: See if I can get it all the way to the back. No I can't. That's embarrassing. Alright. So if n is less than or equal to 1, return n. Well that's not right, right? What should I be doing there? Because Fib of is? What? 1. So let's fix it. How about that, right? Or maybe, what would be even simpler than that? Maybe I should just do that.

Now let's try it. We feel better about this? We like that answer? Yes, no? What's the answer, guys? What should Fibonacci of 6 be? I think that's the right answer, right? OK.

So what do I want you to notice about this? I've computed a value which is 13. And it's taken me 25 calls. 25 recursive calls to get there. Why is it taking so many? Well, what we can see here is that I'm computing the same value over and over again. Because if we look at the recursive structure of the program, what we'll see that's going on here is, I call Fib of 5 and 4, but then Fib of 5 is also going to call Fib of 4. So I'm going to be computing it on those branches. And then it gets worse and worse as I go down.

So if I think about computing Fib of I'm going to be computing that a lot of times. Now, fortunately, Fib of 0 is short. But the other ones are not so short. And so what I see is that as I run this, I'm doing a lot of redundant computation. Computing values whose answer I should already know. That's, you'll remember last time, I talked about the notion of overlapping sub-problems. And that's what we have here. As with many recursive algorithms, I solve a bigger problem by solving a smaller instance of the original problem. But here there's overlap. The instant unlike binary search, where each instance was separate, here the instances overlap. They share something in common. In fact, they share quite a lot in common. That's not unusual.

That will lead me to use a technique I mentioned again last time, called memoization. Effectively, what that says is, we record a value the first time it's computed, then look it up the subsequent times we need it.

So it makes sense. If I know I'm going to need something over and over again, I squirrel it away somewhere and then get it back when I need it. So let's look at an example of that.

So I'm going to have something called fast Fib.

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил