Iteration vs Recursion Fibonacci Exercise

[00:00:00]
>> Anjana Vakil: Moving on, let's talk about the writing side of things, and I'm curious to see whether we still feel the same preferences once we're done with this. Now, we already burned our cliche functional programming function factorial, but we still have one more cliche function left to use, the Fibonacci sequence.

[00:00:20]
Have folks encountered the Fibonacci sequence before? It has to do with the golden ratio and shows up in nature and spirals and all kinds of stuff. You can deep dive on Wikipedia about it. But essentially, it's a sequence of numbers that is Infinite, that starts with 0 and 1.

[00:00:44]
And then each following number is the sum of the previous two numbers, so 0 plus 1 equals1, 1 plus 1 equals 2, 1 plus 2 equals 3 2 plus 3 equals 5, etc., etc. Cool, so this is a sequence that, like I said, it's often useful for things like, aesthetic purposes, and you can read all about it in the Wikipedia article, but for right now, I'm just gonna say do it.

[00:01:13]
So [LAUGH] We need to compute this Fibonacci sequence. Basically, we're gonna compute nth number of the Fibonacci sequence. So these functions, the imperative version and the recursive version, are both gonna take in a number, an integer n, that is like a positive integer, and it's gonna give us the nth number in the Fibonacci sequence.

[00:01:35]
Which means it's gonna be the sum of the previous two numbers. And that, those numbers are going to each be the sum of their previous two numbers, and so on and so forth. So your task is to write two versions of this, one in imperative style with loops, and one in recursive style with a call to recursive Fibonacci, or perhaps more than one call to recursive.

[00:01:59]
To Fibonacci, I don't know, [LAUGH] And get the correct output from the test cases that I've given you here, godspeed.
>> Anjana Vakil: Okay, so how do we feel about these implementations? And the writing side of things versus the reading side of things, let's review and you're going to help me code up the solution here.

[00:02:31]
So, okay, in our imperative Fibonacci, we are in our familiar world of writing commands and telling the program what to do. And we're gonna try to use an iterative loop like we would for a lot of repetitive things in JavaScript. So there are a couple of situations in which I don't even need to loop over anything or like do any kind of complex computation.

[00:03:00]
And those are the first two numbers, right? They're fixed, they're just defined, the first two numbers of the Fibonacci sequence are 0 and 1 period. So those are some cases that might be pretty easy to handle. For example, if I have an N that is 0, like if this person is asking me for the zeroth or the first thing in the Fibonacci sequence, well, I already know what that is, I can just return 0.

[00:03:29]
And likewise, if I have n equals 1, then I already know what the element at index 1 of the Fibonacci sequence should be, it is run boom. So that solves two of the problems, but we still have a whole rest of the natural numbers to deal with here.

[00:03:53]
So let's think about how we are gonna do this iteratively, okay? Cool, we're gonna need some way to remember kind of where we are in the sequence and what values we already know about. If that makes sense, so let's define a couple of variables. We can do, and I'm using a let here because we're gonna mess with them previous, the previous thing like would be conceptually the if n.

[00:04:34]
So now I'm if I'm reaching this line of code 6 here, I already know n is not 0 or 1, and we're assuming n is never gonna be negative or non-injure or whatever like that. So, if I get to line 6, I know I'm dealing with two or higher.

[00:04:48]
And so that means, in order to compute the Fibonacci number at that index, I need to look at the two previous numbers in the sequence. I need to remember those, so I'll have a previous 1. And in this case, let's imagine that that's our like, n minus 2, and then I'm gonna call the other thing we want to remember.

[00:05:11]
I'm going to call it current, just say, like, where are we at? What have we already computed so far in the sequence? And in this case, if we have an n of larger than 2, we already know 0, we already know run, and 1 is kind of as far as we've gotten, so I'll call it current.

[00:05:25]
But if you can think of better names for these variables, please use them. Now what we want to do is start looping and,
>> Anjana Vakil: You might I have used a old school style for a loop, or a new school for of loop here. I'm gonna use an old school style, just because it's very explicit about how imperative the iteration is.

[00:05:54]
So let's start with a 4. And I'm gonna say we're gonna need another way of representing like where we are at in the computation. I'll call it i and when we start out it'll be n and n will be like the next item in the sequence that we need to compute.

[00:06:16]
And we already have computed the item that we're currently kind of up to, and then the previous item. So we're gonna start i at n, there's, we could do this in either direction, basically. I might do it.
>> BLANK_AUDIO].
>> Anjana Vakil: We are making sure that i is always like bigger than one, because we've already handled the one case.

[00:06:39]
And then at each step, we're actually starting from n, so the number that we want and we're moving down towards 1. So we're doing a decrement or dec sorry not n i minus minus a decrement decrement I never know how to pronounce the e in that. But we are going to be moving from n the higher number all the way down through the sequence of the many numbers until 1.

[00:07:05]
And you could do this in the opposite direction, not a huge difference. But so what we're gonna do is we are going to add together the number of the sequence that we are up to and the previous number. Because that's what the sequence is defined by. So I'm gonna have previous plus current happening in here, and I'm just going to capture that in like a new value.

[00:07:34]
I'll call it the next value layer, we're already up to the current value, and now we wanna get the next one that's gonna be previous plus current. And then we wanna swap out these values so that I keep moving through the sequence. And so instead of, I am using 0 and 1, always as those values, I'm gonna keep updating it on every for loop.

[00:08:04]
So what I can do now is make sure that the the current current becomes the new previous. So previous equals current and the new current is gonna be the value I just calculated, which is what I called next. So we're sort of updating these tracker variables, the preview and current as we go through the sequence.

[00:08:38]
And once we've gone through all of the numbers between 1, which we already know the result of, and n, kind of summing them up two at a time. The final thing that we're left with should be the last current value, if you will. The last time that we do an add and then reassign it to current.

[00:09:07]
That's gonna be the value that we want. So we will just return current from here. Let's look at the recursive implementation of the Fibonacci calculator. So here.
>> Anjana Vakil: Well, we still know what the first two numbers of the Fibonacci sequence are right? And because it is a recursive function, we definitely need a base case, at least one wink.

[00:09:35]
And so in this case, honestly, our code is gonna look identical to the first couple of lines of our imperative version, which essentially is going to represent our base cases. So our base cases, we have two of them. Now, if we get 0, we know it's 0, if we get 1, we know it's 1, and then what?

[00:09:57]
Okay, well, when we talk about in human terms, what is the Fibonacci sequence like, how do we think about it? How do we define it? As we saw, we said the next number in the sequence is the sum of the previous two numbers, right? So if we want to know the recursive Fibonacci of n, we can recursively compute the previous two numbers in the sequence and then add them together to get the nth number.

[00:10:38]
And we know that if we get this far, if we get to line 19 here, or yeah, that we we don't have 0, we don't have 1, so we're at least two here. And so what I can do is call our cursive Fibonacci on the previous two numbers, which means I'm gonna call it on the previous number, n minus 1, and also on whoops.

[00:11:04]
And also on the one before that, which is gonna be n-2, and add those together.
>> Anjana Vakil: And return the value. And my goodness I see green in the tests, we did it.