If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

The factorial function

For our first example of recursion, let's look at how to compute the factorial function. We indicate the factorial of n by n!. It's just the product of the integers 1 through n. For example, 5! equals 12345, or 120. (Note: Wherever we're talking about the factorial function, all exclamation points refer to the factorial function and are not for emphasis.)
You might wonder why we would possibly care about the factorial function. It's very useful for when we're trying to count how many different orders there are for things or how many different ways we can combine things. For example, how many different ways can we arrange n things? We have n choices for the first thing. For each of these n choices, we are left with n1 choices for the second thing, so that we have n(n1) choices for the first two things, in order. Now, for each of these first two choices, we have n2 choices for the third thing, giving us n(n1)(n2) choices for the first three things, in order. And so on, until we get down to just two things remaining, and then just one thing remaining. Altogether, we have n(n1)(n2)21 ways that we can order n things. And that product is just n! (n factorial), but with the product written going from n down to 1 rather than from 1 up to n.
Another use for the factorial function is to count how many ways you can choose things from a collection of things. For example, suppose you are going on a trip and you want to choose which T-shirts to take. Let's say that you own n T-shirts but you have room to pack only k of them. How many different ways can you choose k T-shirts from a collection of n T-shirts? The answer (which we won't try to justify here) turns out to be n!/(k!(nk)!). So the factorial function can be pretty useful. You can learn more about permutations and combinations here, but you don't need to understand them to implement a factorial algorithm.
The factorial function is defined for all positive integers, along with 0. What value should 0! have? It's the product of all integers greater than or equal to 1 and less than or equal to 0. But there are no such integers. Therefore, we define 0! to equal the identity for multiplication, which is 1. (Defining 0! = 1 meshes nicely with the formula for choosing k things out of n things. Suppose that we want to know how many ways there are to choose n things out of n things. That's easy, because there is only one way: choose all n things. So now we know that, using our formula, n!/(n!(nn)!) should equal 1. But (nn)! is 0!, so now we know that n!/(n!0!) should equal 1. If we cancel out the n! in both the numerator and denominator, we see that 1/(0!) should equal 1, and it does because 0! equals 1.)
So now we have a way to think about n!. It equals 1 when n=0, and it equals 12(n1)n when n is positive.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

Want to join the conversation?

  • blobby green style avatar for user Anne
    Can someone clarify why 0! = 1? I'm really getting lost on the last paragraph, specifically:

    "It's the product of all integers greater than or equal to 1 and less than or equal to 0. But there are no such integers. Therefore, we define 0! to equal the identity for multiplication, which is 1."
    (33 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      n! is the product of all integers greater than or equal to 1 and less than or equal to n
      or more simply:
      the product of all integers from 1 to n (starting at 1 and going up to n)
      i.e. 1 * 2 * 3 * 4 * 5 * ... * n-1 * n

      so when n=0 we have
      the product of all integers from 1 to 0 (starting at 1 and going up to 0)
      But 1 is already larger than 0 so there are no integers from 1 to 0 (counting up)
      So what do we use for the product of no integers ?
      We use 1.
      Why ?
      Because it is convenient, it makes makes math easier, and most importantly it makes our formulas that could calculate 0! make sense. The article gives an example of how it makes our formulas make sense. It shows that when we calculate the number of ways of choosing a group of n items from n items (which should obviously be 1), the formula needs 0! to be 1.

      Hope this makes sense
      (80 votes)
  • blobby green style avatar for user Maddie Walker
    I'm still really confused on this subject. If one of y'all could explain how n and n! work in a really simple almost kindergarten version, that would be amazing! I'm trying to relate this so something that I have already learned/know about so the concept will be easily identified and understandable. Thanks in advance!
    (9 votes)
    Default Khan Academy avatar avatar for user
  • leafers seed style avatar for user lauren.finkle
    In the for loop when we say result = result * i; how do these two results not override each other? How does the computer know that one result is referring to the previous sum of the multiplications and the other is that value times i?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • starky ultimate style avatar for user jdsutton
      result = result * i; is really telling the computer to do this:
      1. Compute the value of result * i and store it somewhere
      2. Take the stored value and assign result to that value

      When you use the = operator, the entire right hand side is evaluated to some value, and then that value is put into the left hand side variable. Everything is happening in steps, not all at once.
      (12 votes)
  • piceratops sapling style avatar for user Vu Tran
    In the example given above where you have n t-shirts and want to be able to pack only k amount, the given formula is n!/(k!⋅(n−k)!)

    In the permutations course given in the link, the formula is stated to to be n!/(n-k)!

    Can someone explain where the extra k! in the denominator came from?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      n!/(k! (n-k)!) would tell you the number of ways you could pick k t-shirts from n shirts where the order does not matter

      n!/(n-k)! would tell you the number of ways you could pick k t-shirts from n shirts where the order matters e.g. the first shirt you pick you write 1 on it, the 2nd shirt you write 2 on it, etc.

      Dividing by k! accounts for the number of ways each selection of k shirts will be counted.
      e.g. Suppose k= 3 and one possible selection of shirts is shirts: 5, 7 and 13
      You could have picked those shirts in these 3! = 6 different ways:
      5 then 7 then 13 or,
      5 then 13 then 7 or,
      7 then 5 then 13 or,
      7 then 13 then 5 or,
      13 then 5 then 7 or,
      13 then 7 then 5
      (8 votes)
  • blobby green style avatar for user Barbara DiLucchio
    when you are writing python code for any given factorial say one that a user enters like 11. what if you also need to determine which values are odd and which are even is it true that they are always even? do you ever get odd results going down thru the range values?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • leaf green style avatar for user Jesse
      All the results of the factorial function are always even UNLESS it's 1! or 0!. Therefore for all n! such that n doesn't equal 0 or 1 the result is even. That's because 0! and 1! equals 1, which is odd.

      This is because an odd number multiplied by an even number is even, and an even number multiplied by an even number is also even. Therefore for every n! where n > 1 an even number is involved, making the answer even.

      Hope that helped!
      (3 votes)
  • ohnoes default style avatar for user Renan Teixeira Ferraz
    The autograder isn't working for me. The console is showing me that the code works, but the autograder doesn't.
    (3 votes)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user cmb717
    I can not get the next challenge completed what am i doing wrong? Here is my code (edited to only show relevant parts)
    var result = 1;

    for(var i= result; i>=n; i--) {
    n=i*n;
    }

    I looked through the comments for help but all I could find were Cameron's cryptic answers can I have a more firm hint please. (not saying Cameron did a bad job just saying I can not understand their hints)
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Let's review some for loop basics:
      //This for loop will:
      //-begin the counter at start,
      //-do some stuff each loop
      //-then increment counter
      //until the counter exceeds last
      for( var counter = start; counter <= last; counter++){
      //this is the body where we do some stuff
      }


      A simple for loop that would print out the numbers from 1 to 10 would be:
      for( var i = 1; i <= 10; counter++){
      println(i);
      }


      Many find the BASIC version of this a bit easier to understand:
      FOR I=1 TO 10
      PRINT(I)
      NEXT I


      There are a couple of things that you almost never want to do inside the body of the for loop:
      1) change the value of the counter
      2) change the value of the number you are stepping the counter towards e.g. last in the first example

      Doing either of those usually leads to unpredictable behaviour.


      Here's some extra hints using the hint code:
      var factorial = function(n) {
      //this will set the value of result before we start looping
      var result = ;

      //think about calculating n! by hand
      // n! = 1 * 2 * 3 * ... * n-2 * n-1 * n
      // what number do we start at ?
      // what number do we end at ?
      for(var i = ; i <= ; ) {

      //we need to update the value of result here, so that it
      //will be equal to n! by the time we stop looping

      //changing the counter i, or the value that it is going to, would be bad here
      ;
      }

      //we are returning the value of result here
      //so result should now hold the value of n!
      return result;
      };


      Good Luck
      (3 votes)
  • starky ultimate style avatar for user Matthew Narodowg
    my code keeps coming up with this
    message

    Hm, are you hard-coding the number to count up to?
    idk what i'm doing wrong
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      If you put a number in the condition of the for loop you'll get that. e.g. i <= 5

      If you put a number like 5 instead of using a variable, that is what is called "hard coding". Hard coding makes your program work for only one specific input. We want our programs to be flexible and work with different inputs, so we use variables.
      (2 votes)
  • sneak peak yellow style avatar for user SecretCoder
    Why do they have a '!' after numbers like: 0!, 1!, n!
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      From the first paragraph of the article:
      "We indicate the factorial of n by n!. It's just the product of the integers 1 through n. For example, 5! equals 1 * 2 * 3 * 4 * 5 or 120. (Note: Wherever we're talking about the factorial function, all exclamation points refer to the factorial function and are not for emphasis.)"
      (2 votes)
  • female robot grace style avatar for user Eden Washington
    I can't get this completed.. I've done the coding statements as I knew how to do

    But I kept on getting
    "Hm, do all your assertions pass?" for this code I was doing, what do i need to add or fix?

    var result = 1;
    for(var i= 0; i<=n; i++) {
    result=(n+1)*(i+1);
    }
    return result;
    };
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      The above calculation result=(n+1)*(i+1); is incorrect.
      A few things to remember:
      n! = 1 * 2 * 3 * ... * n
      and
      n! = n * (n-1)!
      and
      0! = 1 (which is same as result before the for loop. So, if it skipped the calculations in the for loop it would be nice)
      (2 votes)