Comparing Iterative and Recursive Factorial Functions

Comparing Iterative and Recursive Factorial Functions


What I want to do
in this video is make clear the distinction
between an iterative, or I should say iterative–
I always pronounce it wrong– an iterative function definition
and a recursive function definition. We’ll do it really by
just kind of understanding where the iteration
is happening over here and where the recursion is
happening here on the right. So when we start off,
we see the product is set to be equal to 1. And then we enter our for loop. The for loop really is the
meat of this iterative function definition. And understanding what’s
happening in the for loop, let me make a little table here. So I’m going to 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. Because every iteration
through this for loop, we’re going to evaluate this
business right over here. And then I’m going
to make a column for the new value
of our product. So 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 returns a list, and it returns a list of
the number of elements that we pass number. We pass into it right over here. So if we assume– and
I should have said this from the get-go– let’s assume
that we’re calling– just give me something specific. Let’s say that
this is the result of a call of factorial of 3. So the argument that we
passed a 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 three elements starting at 0. The last element is 3 minus 1. It is 2. And so each loop
through this for loop, i is going to be assigned
to each successive element in this list. So on the first time
through 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, up here before we
even enter the loop, product was defined to be 1. So product is going
to be 1, and it’s 1 times– I don’t want
to do it in that color. I’ll just do it in
magenta– 1 times i, which is 0– 1
times 0, plus 1. And then our new
value or product is essentially this evaluated. We have it right here. Product is equal to
all of this business. And so our new value
is 1 times 0 plus 1. Well, that’s just 1 times 1. And that’s just going to be 1. And that’s all we had
inside the for loop clause, because that’s the
only stuff that was indented within
this for loop. And so then we go
back up, and we’re going to iterate through the
next iteration of our loop, I guess you could say. And now i is going
to be assigned to 1. This expression
over here– we’re going to take our old product. So product is still 1. And it’s 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 iteration through the loop– our
second pass through the loop. And 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’ll now be assigned to 2. So i is now 2. This thing over here,
it’s going to be product. Well product is now 2. So it’s going to be 2 times i. Well i is now 2 plus 1. And so what does this–
this is 2 times 3, or 6. And then it’ll go,
and it’ll say, OK, can we assign i to any
more elements of this? No, we’ve run out of elements. So now we break out
of the for loop, and we just return the product
or the variable product it was referring to. And that’s what I
should really say. We should return the value of
the product is referring to, and that value is 6. So when you call factorial
of 3, it will return 6. So if you were to 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’s what the
function will return. And then you add those up,
and they would evaluate to 12. So this is why we
call it iterative. We kept iterating through
the same set of instructions. Now let’s compare the
recursive definition. And this one is a little bit
more fun in a lot of ways. So once again, we’re going
to call factorial of 3. So 3 is our argument. That’s the value that number
will refer to, it’ll take on. It says if number is
less than or equal to 1. Well, 3 is not less
than or equal to 1. So we’re not going to
do this part over here. We’re going to do
the else clause. So we’re 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, OK, factorial. But now the argument
is 2, so number is 2. We go here. If number is less than
or equal to 1, do this. Well, 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 a factorial
of number minus 1. Well, in this situation,
the number is now 2, and we’re going to
want to multiply that 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 interpreter has
to kind of remember that we’ve made this
whole series of functions calls and has to keep digging
deeper and deeper and deeper. So now we’ve called factorial
of 1, and 1 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 why we call
it a base case. We’re kind of going down to it. So if the number is less
than or equal to 1, return 1. So in this situation, when
we call factorial of 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 that factorial
of 3 evaluates to 3 times 2, which will evaluate to 6. So very different ways
of thinking about it but getting you the
exact same result. Once again, if you
take factorial of 3 plus factorial of
3, it doesn’t matter which way we implement it. We’ll get 6 plus 6, or 12.

29 thoughts to “Comparing Iterative and Recursive Factorial Functions”

  1. Why cant you take a negative factorial with this program?
    Both the iterative and recursive version give 1 as the factorial of any negative

  2. @radiator0505 I think it has to do with the definition of a factorial. It works fine when the numbers are decreasing, but the definition of a factorial given a negative number is different (since the numbers are increasing each time rather than decreasing).. this results in a divide-by-zero error when you get to 1. Why the program returns 1 I am not sure.

  3. I would never guess recursion would ever work because it APPEARS as if you are redefining the value of the variable "number" and returning a result every time the function recurs. The thing that needs explaining for me is how Python knows to remember each of the returned results for each recurring function call.

  4. it works this way: the function is still running while it calls the next function, so it builds up a stack of function calls (thus: call stack), then when it reached the base case, it returns a value, then the above returns, etc. etc. until the call stack has been reduced back to the original function call, which then returns the result, done. the variable number is NOT the same for all the function calls, each function call has its own variables.

  5. This video doesn't provide any comparison like the title says. It's more of a walkthrough of an iterative and recursive example.

  6. Hi, amazing video!
    Check out my online shop at Technology Sponsors website: https://www.facebook.com/TechnologySponsors/app_189977524185

  7. I have to admit, almost went to another video after hearing a mistake in the "iterative" pronunciation within the very first verbal audible of this video.

  8. Very well explanation. So the program stacks the numbers n in memory then go back and solve each multiplication.

  9. I love the concept of Programming.
    But I really hate the method my college book is explaining this.
    Thank you Khan Academy!!!

Leave a Reply

Your email address will not be published. Required fields are marked *