Recursive Factorial Function

Recursive Factorial Function


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.

45 thoughts to “Recursive Factorial Function”

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

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

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

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

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

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

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

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

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

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

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

  12. 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… 🙁

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

  14. //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;
    }

  15. Why are you screaming?

    This is a better explination of what the code is doing.
    https://www.youtube.com/watch?v=ozmE8G6YKww

Leave a Reply

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