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

Recursive factorial

For positive values of n, let's write n! as we did before, as a product of numbers starting from n and going down to 1: n! = n(n1)21. But notice that (n1)21 is another way of writing (n1)!, and so we can say that n!=n(n1)!. Did you see what we just did? We wrote n! as a product in which one of the factors is (n1)!. We said that you can compute n! by computing (n1)! and then multiplying the result of computing (n1)! by n. You can compute the factorial function on n by first computing the factorial function on n1. We say that computing (n1)! is a subproblem that we solve to compute n!.
Let's look at an example: computing 5!.
  • You can compute 5! as 54!.
  • Now you need to solve the subproblem of computing 4!, which you can compute as 43!.
  • Now you need to solve the subproblem of computing 3!, which is 32!.
  • Now 2!, which is 21!.
  • Now you need to compute 1!. You could say that 1! equals 1, because it's the product of all the integers from 1 through 1. Or you can apply the formula that 1!=10!. Let's do it by applying the formula.
  • We defined 0! to equal 1.
  • Now you can compute 1!=10!=1.
  • Having computed 1!=1, you can compute 2!=21!=2.
  • Having computed 2!=2, you can compute 3!=32!=6.
  • Having computed 3!=6, you can compute 4!=43!=24.
  • Finally, having computed 4!=24, you can finish up by computing 5!=54!=120.
So now we have another way of thinking about how to compute the value of n!, for all nonnegative integers n:
  • If n=0, then declare that n!=1.
  • Otherwise, n must be positive. Solve the subproblem of computing (n1)!, multiply this result by n, and declare n! equal to the result of this product.
When we're computing n! in this way, we call the first case, where we immediately know the answer, the base case, and we call the second case, where we have to compute the same function but on a different value, the recursive case.

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?

  • piceratops ultimate style avatar for user Seiji Sakurai
    Would it be appropriate to understand this implementation as mathematical induction?
    (24 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Induction and recursion are closely related.

      Induction starts from the base case(s) and works up, while recursion starts from the top and works downwards until it hits a base case.

      With induction we know we started on a solid foundation of the base cases, but with recursion we have to be careful when we design the algorithm to make sure that we eventually hit a base case.

      Often when we want to prove a recursive algorithm is correct we use induction. (We also need to include a proof that the algorithm terminates)
      (87 votes)
  • leaf green style avatar for user yang liu
    var factorial = function(n) {
    var result=n-1;
    // base case:
    if (n === 0 ) {return 1;}
    // recursive case:
    else if (n >0) {
    for (var i =1; i <n-1 ; i++){
    result = result*i;
    return n*result;}

    why i cant pass the second step of challenge? need some help~~~
    (7 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      It's not working because your solution is an iterative solution, not a recursive solution.
      A recursive solution would involve the function calling itself (Hint: your recursive case should fit on one line, and shouldn't have a for loop)
      (23 votes)
  • mr pants teal style avatar for user bhagerty
    This is a very clear explanation, but I wonder if you might want to include some cautionary language about using recursion in the real world. In Steve McConnell's book Code Complete, he says this (p. 397) about recursion and factorials:

    "One problem with computer-science textbooks is that they present silly examples of recursion. The typical examples are computing a factorial or computing a Fibonacci sequence. Recursion is a powerful tool, and it's really dumb to use it in either of those cases. If a programmer who worked for me used recursion to compute a factorial, I'd hire someone else. . . . In addition to being slow and making the use of run-time memory unpredictable, the recursive version of [a factorial-computing] routine is harder to understand than the iterative version . . . ."

    Now, I understand that factorials are a pretty easy way to teach recursion, and I understand that Code Complete is very opinionated. But wouldn't it be worth alerting the learner to the possibility of criticism like McConnell's? Food for thought.
    (11 votes)
    Default Khan Academy avatar avatar for user
  • mr pink red style avatar for user Bob Everton
    in the next challenge you refer to "base case", what is "base case"?
    (5 votes)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user NelsonDaniel
      Base case is where the value of the function is specified in one or more values of the parameter. It is where you ask yourself: Is there a non-recursive way out of the function?
      Trivial cases of the function.
      In factorial if n = 0 then n! =1 // non-recursive part or base case
      otherwise if n>0 ---> n! = (n-1)! // recursive case
      (7 votes)
  • orange juice squid orange style avatar for user Doctor137
    Is it possible to find the factorial value of a negative number? Or is it always 1?
    (5 votes)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user The Space Goat
    Wait, what makes this any more efficient than the simple algorithm we wrote in the last challenge? This seems unnecessarily complicated.
    (4 votes)
    Default Khan Academy avatar avatar for user
  • leaf blue style avatar for user Miki  Munna
    Could someone please help me.

    I made a program for factorial by using C++.
    At first I did it using the recursion method.But found that the factorial function gives wrong answer for input values of 13, 14 and so on. It works perfectly until 12 as the input.
    To make sure my program is correct I used iteration method using the "while loop". But that also gave me the same result; incorrect answer after 12.
    I crosschecked with my calculator (CASIO fx-991MS).

    But with javascript the function runs perfectly.

    Here is my program using C++ in codeBlocks:

    #include <iostream>
    using namespace std;

    //using recursion
    int factorial(int x){
    if(x == 0){
    return 1;
    return x*factorial(x-1);


    //using iteration
    int Factorial(int x){
    int factorialValue = 1;
    while(x > 0){
    factorialValue *= x;
    cout << factorialValue << endl;


    int main()
    //calling for the recursion function
    cout << factorial(13) << endl;

    //Calling for the iteration function

    return 0;
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      The problem is the code above uses the int type. The int type in C++ is 32 bits, so it only has a range of:
      -2^31 to 2^31-1

      Since 13! is larger than that it starts to overflow and gives crazy answers. Try using the long long or long long int type which uses 64 bits so it can store numbers from:
      -2^63 to 2^63-1
      (3 votes)
  • blobby green style avatar for user mac
    this is not helpful
    (3 votes)
    Default Khan Academy avatar avatar for user
  • leaf grey style avatar for user MFalcon
    How could you simplify this process with larger numbers? For example if I had to calculate 100! ,
    Could I multiply 5! by 20! How do you divide as well?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Barbara DiLucchio
    I'm trying to figure out the results of a python code problem that could be a math problem but if a user inputs a random value of how they want to calculate factorial. Say they put in 11. then after you have dealt with the < 0 and if it == 1 then you have to go thru a range like this;

    for i in range(1, num + 1):
    if 5%2 == 0:
    # Python program to find the factorial of a number provided by the user.

    # change the value for a different result
    num = 7

    # uncomment to take input from the user
    #num = int(input("Enter a number: "))

    factorial = 1

    # check if the number is negative, positive or zero
    if num < 0:
    print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
    print("The factorial of 0 is 1")
    for i in range(1,num + 1):
    factorial = factorial*i
    print("The factorial of",num,"is",factorial)

    Does this always come out even or is it odd every other one?
    I am missing something. Please help me to unerstand
    (2 votes)
    Default Khan Academy avatar avatar for user