What I want to do in this

video is introduce you to what I think is one of

the neatest ideas in computer science, and that is recursion. So the way that we’ve defined

this factorial function in the last few

videos is actually an iterative definition. We are iterating

through different values for this variable

i, and then we’re essentially taking those values,

adding one, then multiplying those times our

original product. And when we keep iterating

through all of that, our eventual product

has all of the values from 1 through the number

multiplied by each other, and they’re all sitting

in this variable product. What I’m going to do here

is rewrite this program. And what’s cool

about functions– I’m going to rewrite

this function. What’s cool about functions

are this function, we just say, look, it returns

a factorial of a number. We don’t care how this

is actually written. And so anything that’s

using this function call, no matter how I implement

it, as long as I implement it correctly, it shouldn’t

worry about it. So as long as I implement the

guts of this function right, even if I do it in a

very different way, it shouldn’t affect the

behavior of any of the functions that call it. So let’s go ahead and try

to define this function recursively. And I think you’re going to

find this slightly fascinating. So I’m going to do it

a little bit different. We’re going to put some

conditionals in here as well. So I’m going to say– so

it’s almost– in some ways, recursion is really

deep and complicated, and on some levels, it’s way

simpler than anything else. So let me just put all

of this stuff down there. So I’m going to say, look,

if the number– you always want to think about a base case. What’s a situation where kind

of the nugget or the smallest values we can put into

for a number that’ll give us a decent response? So we’ll say, look,

if number is– let’s say if it’s less

than or equal to 1, so if it’s less than or equal

to 1, let’s just return. Well, then it’s factorial. Let’s just return

1, especially if we want to have the same

behavior as the old function. The old function,

regardless of whether we put a 1 there, a 0

there, or actually, even if we put a negative

1 or negative 2 there, it always gave us the

factorial being equal to 1. So that’s exactly what

we’re doing over here. We’re returning 1 if the

number is less than 1. And this also defines

our base case. I can even label it here. So let me label–

this is our base case. And you’ll see what I mean

for a second by base case. And what I’m about

to do now, this is the really exciting

part about recursion. If the number is not

less than or equal to 1, so I could write

l if– well, maybe I’ll just write l, actually. So if the number is not

less than or equal to 1, I’m going to return

something different. And what I’m going to

return is that number times the factorial–

times the factorial of one less than that number. Now, the reason why this

is fascinating and cool and all the rest is I

just defined something using that something. So I just defined a

function called factorial, and I defined it using the

definition of the function factorial. It is referring to itself. This is what recursive

functions do. But if you think about it–

and I’ll diagram it out in more detail in

the next video, so hopefully it makes a

little bit more sense– it should kind of work. Because if you put a 1

or a 0 in for a number, it’ll just return 1. What happens if the number is 2? Well, if the number

is 2, it’ll say, look, the number is not less than

our 1, so I’ll go over here. So it says it’ll return 2

times factorial of 2 minus 1, or factorial of 1. And then it’ll call factorial

again, and factorial of 1 is just 1, so it’ll

return 2 times 1. So that’ll work out for 2. Try it for 3. If you do a

factorial of 3, it’ll go down to this

clause over here, because 3 is not less

than or equal to 1, and it’ll return 3 times

the factorial of 3 minus 1, which is 2, the factorial of 2. Well, we know it already

returns the right answer for the factorial of 2, so

it’ll return 3 times 2, which is 6, which is a factorial of 3. So hopefully you’re

getting the gist of it. Factorial of 4 is going to

work for the exact same reason. It’s going to boil down to

4 times the factorial of 3. We know that it works

for the factorial of 3. And just to prove

to you that I’m not doing some type of crazy voodoo,

and that this will actually work, let’s try to

run the program. Let’s try to run the

program right here. This is some stuff that

I was doing beforehand. Let me just get rid of that. So let’s just run the program. So all I’ve done

is I’ve redefined the factorial function, but

I’ve redefined it recursively. I won’t have to

change the comments. So let me save it, and let’s

interpret this program. Let’s execute it and see if

it does what we need it to do. All right. So they’re prompting

us for something. Let’s take the

factorial of 5– 120. And so once again,

our factorial program, no matter what we put in there,

it gives us the right answer. But what’s really cool is

it’s now doing it recursively. When I do factorial of 6,

say, OK, factorial of 6. Is 6 less than or equal to 1? Well, no it’s not, so

it goes to this else clause right over here. So then it says return 6

times the factorial of 5. Then it says, OK,

let me remember 6 times the factorial of 5. Let’s figure out what

the factorial of 5 is. Well, factorial of 5 is going to

be 5 times the factorial of 4. And then that factorial of 4

is 4 times the factorial of 3, all the way down to the

factorial of 1, which is 1. And so it’ll actually return 6

times 5 times 4 times 3 times 2 times 1.

FIRST!!!!

Thank you for these videos, Khan!

Although I already know all of this stuff so far, it's still interesting to see how you teach it and listen in just for the fun of it.

Please do with java or c++

thanks man

He's just describing mathematical functions, this can also be translated to C++ or Java or anything quite simply, just know how to work math in the language of your choosing.

@riyadhelalami Java and C++ are great languages. But I think Sal is just trying to do basic computer science. Python is great for that because there is zero boilerplate code. If he did this in Java, he would have to surround this in a main function, and surround that main function in a class. Then he would have to explain those things, and that would distract from what he's trying to teach.

Python is the most neutral language he could have chosen as it is not focused around a specific paradigm. It really isn't hard to translate these ideas from one language to another.

is this language similar to matlab??? we use matlab in my university

u don't have to press 3 spaces. u can press a 1 tab.

I think this is his response to thenewboston doing the Geometry tutorials

Thanks for the great video. I should warn you though – python has a very shallow stack frame, 1000 frames max. Then it'll be a stack overflow.

@m1o2 It's a general rule of thumb to use 4 spaces instead of a tab, dunno exactly why but most Python scripters swear by it.

Yay I got so excited that you're finally teaching computer science!

@prcrazy12345 Syntactically, it bears a passing resemblance to matlab. But fundamentally, they are tools for completely different jobs. Python is a general purpose programming language. This means that, with enough effort, you can adapt it to pretty much any computer science problem you can think of. Matlab on the other hand is a domain-specific language. It is engineered to be highly useful in a specific set of problems(math and graph plotting), and not so useful outside that domain.

@armpitpuncher thats what i wanted to know, thanks a lot!!!

Because recursion is heavy on the stack(a part of memory). When you call factorial, some data goes onto the stack. The value of n, as well as some other meta data. When factorial calls itself, that data is still there, then the new call puts its own copy of n, and similar meta data, onto the stack. So, the higher the value of n, the more space the function takes up on the stack. Space on the stack is limited, so if n is high enough, the space runs out. That's why it fails.

@DivergentMind This is why, while recursion is really neat, in many situations, it's just not practical. One of my favorite algorithms is the flood-fill algorithm, which most people have seen in action in any bitmap editing program. It lends itself to an elegant recursive solution, unfortunately, in any normal screen sized image, it results in a stack overflow. So you have to come up with an alternative, less elegant iterative solution.

while(true):

print "recursion works because "

hey sal great video, but instead of putting if n<=1, u could have just tried if n==0, works just as fine, otherwise thanks for the great video, really helped

Mind = Blown

wow thanks

Mind = blown

khanacademy should hire phpacademy and thenewboston for its programming tutorials. I think if they collaborate it would really be something awesome.

slightly fascinating? dude, that's mind-blowing

I copied this exact script into 3 different versions of python and got Syntax Error: (factorial_of_user_input) invalid syntax for all 3. Doesnt even ask me to input any numbers… 🙁

none of this code works for me

every time I get SyntaxError: invalid syntax

what am I doing wrong?

please help

Sometimes you are correct. Recursion can be written in a way that causes issues where it fills up the stack and causes memory problems. But, you can use a language that takes advantage of things like tail-recursion or write your recursive functions in a smarter way that doesn't cause these problems.

So, it is not just theoretical. Many algorithms can take advantage of recursion to make their implementation incredibly simple. Recursion is just a tool like for/while loops.

this is very well explained

crazy voodoo lmao

//Java with Single Entry Single Exit (SESE)

public long calcNFactorialRecursive(int n)

{

long factorial;

if (n == 0) {

factorial = 1;

}else{

factorial = n * calcNFactorialRecursive(n – 1);

}

return factorial;

}

Mind bending weird.

Dude you saved my ass

thanks heaps, I watched some videos, but only yours helped!!!!

Thank you again!

The only video that properly explains recursion in Python on Youtube…

I can't find these videos on Khan academy website

thank you

thank you Khan once again you have saved me 🙂 you'r a true Genius

Why are you screaming?

This is a better explination of what the code is doing.

https://www.youtube.com/watch?v=ozmE8G6YKww

If only this "recursion" would work:

Read moreHow can I write "is not less than " in python as a symbol?

thank you^^

Rip headphone users at 2:58

good explanation sir, keep it up 👍👍

Thank you

Thanks sir

very informative video

I should get points for watching this. Put this on the Khan Academy website!