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.

second. lol

I love this guy

python is the shit!

Recursion blows my mind.

Why cant you take a negative factorial with this program?

Both the iterative and recursive version give 1 as the factorial of any negative

@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.

YOU'RE AWESOME, THANKS!!!

Sal, watching this playlist makes me want to switch my major to CS :(:(:(

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.

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.

you can't explain recursions with functions in 2 minutes…

In maths, factorial of negatives don't really exist. The functions give 1 when they should say doesn't exist.

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

Just had one of those "Oooooooh" moments. Thanks Khan!

Hi, amazing video!

Check out my online shop at Technology Sponsors website: https://www.facebook.com/TechnologySponsors/app_189977524185

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.

Thank you.

Absolutely wonderful explanation of recursion. Well done!

thanks a lot

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

Must I always return 1

the way you write it and show it here was enlightening for me

hey tech me if we put njmber=1 in if statement so ans is 1 how

What does return do ?

note, that i + i should be i + 1? yes?

Thanks god you're here.

eyeteration

I love the concept of Programming.

But I really hate the method my college book is explaining this.

Thank you Khan Academy!!!

So iterative basically means you use a for loop instead of recursion.. okay