Would it be appropriate to understand this implementation as mathematical induction?

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)

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~~~

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)

in the next challenge you refer to "base case", what is "base case"?

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. Example: In factorial if n = 0 then n! =1 // non-recursive part or base case otherwise if n>0 ---> n! = (n-1)! // recursive case

Wait, what makes this any more efficient than the simple algorithm we wrote in the last challenge? This seems unnecessarily complicated.

You will find that the implementation is quite simple. This is just a basic example to introduce you to the idea of recursion. In practice you really should not compute factorials recursively.

Is it possible to find the factorial value of a negative number? Or is it always 1?

What would a negative factorial be? It would just be -(5!), or -( 5 x 4 x 3 x 2 x 1) So you could just ignore the negative symbol, and add it at the end.

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?

You could store some of the calculations in an array and access the values when needed. Google dynamic programming if you're interested in optimization.

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; }else{ return x*factorial(x-1); } } //using iteration int Factorial(int x){ int factorialValue = 1; while(x > 0){ factorialValue *= x; x--; } cout << factorialValue << endl; } int main() { //calling for the recursion function cout << factorial(13) << endl; //Calling for the iteration function Factorial(13); return 0; }

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

Why is a factorial an exclamation point

Christian Kramp was the first to use an exclamation point to signify a factorial. Here's his Wikipedia page: https://en.wikipedia.org/wiki/Christian_Kramp

Main content

Recursive factorial

Q: 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~~~

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)

Q: in the next challenge you refer to "base case", what is "base case"?

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. Example: In factorial if n = 0 then n! =1 // non-recursive part or base case otherwise if n>0 ---> n! = (n-1)! // recursive case

Q: 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; }else{ return x*factorial(x-1); } } //using iteration int Factorial(int x){ int factorialValue = 1; while(x > 0){ factorialValue *= x; x--; } cout << factorialValue << endl; } int main() { //calling for the recursion function cout << factorial(13) << endl; //Calling for the iteration function Factorial(13); return 0; }

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

Q: Why is a factorial an exclamation point

Christian Kramp was the first to use an exclamation point to signify a factorial. Here's his Wikipedia page: https://en.wikipedia.org/wiki/Christian_Kramp

Google Classroom

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, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. But notice that left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 is another way of writing left parenthesis, n, minus, 1, right parenthesis, !, and so we can say that n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, !. Did you see what we just did? We wrote n, ! as a product in which one of the factors is left parenthesis, n, minus, 1, right parenthesis, !. We said that you can compute n, ! by computing left parenthesis, n, minus, 1, right parenthesis, ! and then multiplying the result of computing left parenthesis, n, minus, 1, right parenthesis, ! by n. You can compute the factorial function on n by first computing the factorial function on n, minus, 1. We say that computing left parenthesis, n, minus, 1, right parenthesis, ! is a subproblem that we solve to compute n!.

Let's look at an example: computing 5!.

You can compute 5! as 5, dot, 4, !.
Now you need to solve the subproblem of computing 4!, which you can compute as 4, dot, 3!.
Now you need to solve the subproblem of computing 3!, which is 3, dot, 2, !.
Now 2!, which is 2, dot, 1, !.
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, !, equals, 1, dot, 0, !. Let's do it by applying the formula.
We defined 0! to equal 1.
Now you can compute 1, !, equals, 1, dot, 0, !, equals, 1.
Having computed 1, !, equals, 1, you can compute 2, !, equals, 2, dot, 1, !, equals, 2.
Having computed 2, !, equals, 2, you can compute 3, !, equals, 3, dot, 2, !, equals, 6.
Having computed 3, !, equals, 6, you can compute 4, !, equals, 4, dot, 3, !, equals, 24.
Finally, having computed 4, !, equals, 24, you can finish up by computing 5, !, equals, 5, dot, 4, !, equals, 120.

So now we have another way of thinking about how to compute the value of n, !, for all nonnegative integers n:

If n, equals, 0, then declare that n, !, equals, 1.
Otherwise, n must be positive. Solve the subproblem of computing left parenthesis, n, minus, 1, right parenthesis, !, 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?

Sort by:

Seiji Sakurai
Posted 9 years ago. Direct link to Seiji Sakurai's post “Would it be appropriate t...”
Would it be appropriate to understand this implementation as mathematical induction?
Button navigates to signup pageComment on Seiji Sakurai's post “Would it be appropriate t...”
(24 votes)
Answer
- Cameron
  Posted 9 years ago. Direct link to Cameron's post “Induction and recursion a...”
  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)
  Comment on Cameron's post “Induction and recursion a...”
  (83 votes)
yang liu
Posted 8 years ago. Direct link to yang liu's post “var factorial = function(...”
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~~~
Button navigates to signup pageButton navigates to signup page
(6 votes)
Answer
- Cameron
  Posted 8 years ago. Direct link to Cameron's post “It's not working because ...”
  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)
  Comment on Cameron's post “It's not working because ...”
  (20 votes)
Bob Everton
Posted 8 years ago. Direct link to Bob Everton's post “in the next challenge you...”
in the next challenge you refer to "base case", what is "base case"?
Button navigates to signup pageButton navigates to signup page
(5 votes)
Answer
- NelsonDaniel
  Posted 8 years ago. Direct link to NelsonDaniel's post “Base case is where the va...”
  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.
  Example:
  In factorial if n = 0 then n! =1 // non-recursive part or base case
  otherwise if n>0 ---> n! = (n-1)! // recursive case
  Comment on NelsonDaniel's post “Base case is where the va...”
  (7 votes)
bhagerty
Posted 4 years ago. Direct link to bhagerty's post “This is a very clear expl...”
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.
Button navigates to signup pageButton navigates to signup page
(7 votes)
Answer
The Space Goat
Posted 7 years ago. Direct link to The Space Goat's post “Wait, what makes this any...”
Wait, what makes this any more efficient than the simple algorithm we wrote in the last challenge? This seems unnecessarily complicated.
Button navigates to signup pageButton navigates to signup page
(4 votes)
Answer
- jdsutton
  Posted 7 years ago. Direct link to jdsutton's post “You will find that the im...”
  You will find that the implementation is quite simple. This is just a basic example to introduce you to the idea of recursion. In practice you really should not compute factorials recursively.
  Comment on jdsutton's post “You will find that the im...”
  (6 votes)
Doctor137
Posted 5 years ago. Direct link to Doctor137's post “Is it possible to find th...”
Is it possible to find the factorial value of a negative number? Or is it always 1?
Button navigates to signup pageButton navigates to signup page
(4 votes)
Answer
- Tareq
  Posted 5 years ago. Direct link to Tareq's post “What would a negative fac...”
  What would a negative factorial be? It would just be -(5!), or
  
  -( 5 x 4 x 3 x 2 x 1)
  
  So you could just ignore the negative symbol, and add it at the end.
  Button navigates to signup page
  (3 votes)
MFalcon
Posted 8 years ago. Direct link to MFalcon's post “How could you simplify th...”
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?
Button navigates to signup pageButton navigates to signup page
(3 votes)
Answer
- dashpointdash
  Posted 8 years ago. Direct link to dashpointdash's post “You could store some of t...”
  You could store some of the calculations in an array and access the values when needed.
  Google dynamic programming if you're interested in optimization.
  Button navigates to signup page
  (2 votes)
Miki Munna
Posted 3 years ago. Direct link to Miki Munna's post “Could someone please help...”
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;
}else{
return x*factorial(x-1);
}

}

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

}

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

//Calling for the iteration function
Factorial(13);

return 0;
}
Button navigates to signup pageButton navigates to signup page
(2 votes)
Answer
- Cameron
  Posted 3 years ago. Direct link to Cameron's post “The problem is the code a...”
  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
  Comment on Cameron's post “The problem is the code a...”
  (2 votes)
Gwendo1r
Posted 6 years ago. Direct link to Gwendo1r's post “Why is a factorial an exc...”
Why is a factorial an exclamation point
Button navigates to signup pageButton navigates to signup page
(0 votes)
Answer
- Captain Cryptic
  Posted 6 years ago. Direct link to Captain Cryptic's post “Christian Kramp was the f...”
  Christian Kramp was the first to use an exclamation point to signify a factorial. Here's his Wikipedia page:
  https://en.wikipedia.org/wiki/Christian_Kramp
  Button navigates to signup page
  (5 votes)
Barbara DiLucchio
Posted 4 years ago. Direct link to Barbara DiLucchio's post “I'm trying to figure out ...”
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:
print("even")
else:
print("odd")
# 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")
else:
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
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Cameron
  Posted 4 years ago. Direct link to Cameron's post “All factorials >= 2! are ...”
  All factorials >= 2! are even since they all contain 2 as a factor. Remember that:
  n! = n * (n-1) * ... * 2 * 1
  Button navigates to signup page
  (1 vote)

Computer science

Course: Computer science > Unit 1

Recursive factorial

Want to join the conversation?