Memoized Fibonacci visualization

- [Instructor] This is a JavaScript function that generates the nth fibonacci number using recursion as well as memoization. So we're gonna go through it and see what the computer actually does behind the scenes. So the first thing it does is declare this data structure which is an empty JavaScript object called memo and that's where the memoization is going to happen later. Then it defines the fib function. And finally it calls the fib function with the input value of five, so the first thing that happens is that we're in fib function with N of five. This first condition is false 'cause N is not zero and it's not one, the second condition is false because five is not in the memo data structure which is completely empty and this third condition is where we're gonna go into. Well it's not really a condition is it? So we go into this else block and it wants to calculate what fibonacci five is by calling fib of N minus one plus fib of N minus two. So what it first does is call fib of N minus one so that's gonna be fib of four so it immediately calls that and now we're in the fib function with N equals four. This is false, this is false, so we're here again and this time it wants to calculate the result of fib three plus fib two. So it first calls fib three and we're in fib for fib equals three, this is false, this is false, and now we're gonna calculate fib three as being fib two plus fib one. It immediately calls fib two so we're in fib for N equals two this is false, this is false, and it's gonna calculate fib two as being fib one plus fib zero. So it immediately calls fib one and now finally this is true so it's gonna return N which is one again. And it'll end up going back to the fib function when N was two because now it's got the result of that first fib call. So now it needs to call fib zero and get that result. So we're in fib for N equals zero, now that first condition is true again so it's going to return N which is zero and come back to when fib was two, when N was two and now it has a result, so now it can update the memo object with the result for N of two and we can see indeed that the object updates over there. And then it returns the result for fib two. All right so now we're back up to fib three and fib three we've called fib two so now it wants to call fib one. So we're back in when N equals one, it once again returns one and now it knows what fib three is it's got a result of two, it can update the memo structure with that result and return it. So now we're back in when N was four and it already calculated fib three, so now it needs to call fib two and this time when it calls fib two and N equals two, it finds that N is indeed in the memo data structure so it can return the value for N equals two from that structure so it's going to get that result of one and it doesn't have to do the recursive calculation. So now we're back with N equals four and now we know what fib four is it's three, we can update the memo and return. Now finally we're back up to when N is five in the fib function it's called fib four and then it just needs to call fib three, so we see it's false but then here three is in the memo structure so it can return the value in the memo structure which is two and go back up here. Now it knows that fib of five is five and it can update the memo structure with that result and return it. Whew and now the whole memoized recursive function is done.