Comparing Iterative and Recursive Factorial Functions

⇐ Use this menu to view and help create subtitles for this video in many different languages. You'll probably want to hide YouTube's captions if using these subtitles.

Comparing Iterative and Recursive Factorial Functions : Comparing iterative and recursive factorial functions

相關課程

0 / 750

what I want to do in this video is make it clear
the distinction between
an I-rative, or I should say iterative,
I always pronounce it wrong
iterative function definition
and a recursive function definition
We'll do it really by... Just kinda understanding where the interation is happening over here
and where the recurssion is happening here on the right.
So when we start off we see that product is set to be equal to 1
and then we enter our for loop and the for loop really is the meat of this interative function definition.
And understanding what's happening in the for loop let's... Let me make a little table here.
So I'm gonna make a table for the value of our variable i and I'll also figure out what the value of
product times i plus 1,
cuz every interation to this for loop we are going to evaluate this bussiness right over here
and then I'm going to make a calumn for the new value of our product, the new value of our product.
Let me underline these things and then we have the new value of our product.
So we learned in many videos ago that in python we say for i in range.
This range part right over here...
This range part right over here returns a list and it returns a list of the number of elements
that we have passed number... We passed into it right over here.
So if we assume and I should have said it from the get code.
Let's assume that we are calling just to make something specific,
let's say this is the result of a call of factorial of 3.
So the argument that we passed this factorial is 3 so the variable number will refer to 3.
So when you call range of number it will literally return a list: 0, 1, 2.
So 3 elements starting at 0, the last element is 3 minus 1. It is 2.
And so each loop trough this for loop i is going to be assigned to each sucessive element
in this list.
So on the first time trough this for loop i is going to be assigned to 0.
So our i is going to refer to 0.
And then product times i plus 1, well in this first loop product appeared before we even entered the
loop, product was defined to be 1.
So product is going to be 1 and it is 1 times -- I don't want to do it in that colour, I'll just do it
in mag... I'll do it in magneta -- 1 times i which is 0. 1 times 0 plus 1.
Plus 1 and this... and then our new value of product is essentially this evaluated,
we have it right over here.
Product is equal to all of this bussiness.
So our new value is 1 times 0 plus 1 and that's just 1 times 1 and that's just going to be 1.
That's all we had inside the for loop clause,
cuz that was the only stuff that was intended within this for loop
and then so we go back up and we are going to interate trough the next interation of our loop.
I guess you could say and now i is going to be assigned to 1.
So now i is going to be 1.
This expression over here, we are going to take our old product.
So product is still 1, so product is 1 and it is going to be times i which is now 1 plus 1.
And what's this going to be equal to?
Well if you evaluate all of this you get 1 times 2 so now the new value for product is 2.
After our second interation trough the loop our second pass trough the loop.
Now it will go back to the beginning of the for loop and i will be assigned to the next element in the
list. It wil be now assigned to 2.
So i is now 2. This thing over here, we are going to take...
This is going to be product. Product is now 2.
So it's going to be 2 times i, well i is now 2 plus 1 and so what is this, it's 2 times 3 or 6.
Or 6 and then it will go and we'll say okay, can we assign i to any more elements in this?
No we have run out of elements so we brake out of the for loop and we just return the product.
Or the variable product, what it's referring to and that's what I should really say.
We should return the value that the product is referring to and that value is 6.
So when you call factorial 3 it will return 6.
So if you were to say factorial, if you say factorial of 3 plus factorial of 3
and you were to evaluate this expression this expression would evaluate to 6
and this expression over here would evaluate to 6 because that is what the function would return
and then if you add those up they would evaluate to 12.
So this is why we call it interative.
We kept interating trough this same set of instructions and now let's compare the recurssive definition.
And this one is a little more fun in a lot of ways.
Once again we are going to call factorial of 3.
Factorial of 3.
So 3 is our argument. That's the value that number will refer to and it will take on
and says if number is less than or equal to 1.
Well 3 is not less than or equal to 1.
So we are not gonna do this part over here.
We are going to do else clause.
So we are going to return number. We are going to return number times factorial of all of this.
So this is going to evaluate to number which is 3. That's the argument we passed.
Times factorial of number minus 1.
Well number minus 1 is going to evaluate to 2. 3 minus 1 is 2.
So times factorial of 2.
Well that's just another function called a factorial so we go back.
Okay, factorial but now the argument is 2. so the number is 2.
We go here. If number is less than or equal to 1 we do this,
but the number isn't less than or equal to 1. It's 2. So now we do else.
So what we now want to return is the number times the factorial number minus 1.
Well in this situation...
In this situation the number is now 2 and we are gonna want to multiply that times the factorial...
times the factorial of 2 minus 1.
Well 2 minus 1 is just 1.
Times the factorial of 1.
Well we just made another function call so the interpretator kinda has to remember that we made this
whole series of function calls and has to keep digging deeper and deeper and deeper.
So now we have called factorial of 1.
Factorial of 1. What is the argument? Number is referring to 1.
If number is less than or equal to 1.
Number is less than or equal to 1.
Now this is what we call a base case. We are kinda going down to it.
So the number is less than or equal to 1. Return 1.
So in this situation, when we call factorial 1 it literally returns 1.
And so we now know that factorial of 2 evaluates to 2 times 1.
So this evaluates to 2 and now we know factorial of 3 evaluates to 3 times 2 which will evaluate to 6.
So very different ways of thinking about it, but getting the exact same result.
Once again if you take factorial of 3 plus factorial 3, it doesn't matter which way we implement it.
We'll get 6 plus 6 or 12.

留言:

載入中...

新增一則留言(尚未登入)

comparing iterative and recursive factorial ... 討論區:

載入中...