How to find the factorial of a number in Java in both recursive and iterative ways is a common Java interview question mostly asked at the fresher level. It’s not just popular in Java interviews but also in other programming languages like C or C++. It's also famous In our last article we have seen how to check if a number is prime or not and in this Java programming tutorial, we will see a simple Java program to find the factorial of a number in Java by using recursion and iteration. The same program can also be used to print factorial of any number or print a range of factorial as well.
Let’s talk about logic, the factorial of a number is calculated by formula number*(number -1) till zero and since the value of factorial zero is 1, it acts as a base case in the recursive version of the factorial method.
Let’s talk about logic, the factorial of a number is calculated by formula number*(number -1) till zero and since the value of factorial zero is 1, it acts as a base case in the recursive version of the factorial method.
The logic to find the factorial of a number is encapsulated inside the factorial(int number) and fact(int number) methods.
This Java programming tutorial is in next with my earlier tutorial for beginners like Java Program to reverse String in Java with recursion, Java program to free memory in java and recently how to read and write to a text file in Java, etc if you haven’t read them you may find them interesting and useful.
How to find factorial of a number in Java using recursion and iteration :
In this section, we will see a complete code example of a Java program to calculate the factorial of a number in both recursive and iterative ways. If you look closely you will find that the recursive solution of calculating factorial is much easier to write and pretty intuitive to read as it represents formula number*(number -1).
Any way recursion should only be limited for educational purposes as it is always subject to stack overflow error if recursion is too deep.
Any way recursion should only be limited for educational purposes as it is always subject to stack overflow error if recursion is too deep.
Calculating factorial of a number is also a good programming question to exercise for anyone who is just started learning to program.
Anyway here is an example of Java program to find factorial of a number :
/**
* Simple Java program to find the factorial of a number using recursion and iteration.
* Iteration will use for loop while recursion will call method itself
*/
public class FactorialInJava{
public static void main(String args[]) {
//finding factorial of a number in Java using recursion - Example
System.out.println("factorial of 5 using recursion in Java is: " + factorial(5));
//finding factorial of a number in Java using Iteration - Example
System.out.println("factorial of 6 using iteration in Java is: " + fact(6));
}
/*
* Java program example to find factorial of a number using recursion
* @return factorial of a number
*/
public static int factorial(int number){
//base case
if(number == 0){
return 1;
}
return number*factorial(number -1); //is this tail-recursion?
}
/*
* Java program example to calculate factorial using while loop or iteration
* @return factorial of a number
*/
public static int fact(int number){
int result = 1;
while(number != 0){
result = result*number;
number--;
}
return result;
}
}
Output:
factorial of 5 using recursion in Java is: 120
factorial of 6 using iteration in Java is: 720
* Simple Java program to find the factorial of a number using recursion and iteration.
* Iteration will use for loop while recursion will call method itself
*/
public class FactorialInJava{
public static void main(String args[]) {
//finding factorial of a number in Java using recursion - Example
System.out.println("factorial of 5 using recursion in Java is: " + factorial(5));
//finding factorial of a number in Java using Iteration - Example
System.out.println("factorial of 6 using iteration in Java is: " + fact(6));
}
/*
* Java program example to find factorial of a number using recursion
* @return factorial of a number
*/
public static int factorial(int number){
//base case
if(number == 0){
return 1;
}
return number*factorial(number -1); //is this tail-recursion?
}
/*
* Java program example to calculate factorial using while loop or iteration
* @return factorial of a number
*/
public static int fact(int number){
int result = 1;
while(number != 0){
result = result*number;
number--;
}
return result;
}
}
Output:
factorial of 5 using recursion in Java is: 120
factorial of 6 using iteration in Java is: 720
That's all on how to calculate or find the factorial of a number in Java. Both iterative and recursive versions of factorial can be used to calculate factorials but beware of StackOverFlowError if a larger number is passed to the recursive version of the factorial method in Java.
Now is the quiz time, what is the time and space complexity of this solution? how slow or fast your program become in order to calculate factorial of larger numbers and how can you solve that problem so that your program remains fast?
14 comments :
Just for the sake of completeness (which you undoubtedly know):
/**
* Tail recursive factorial.
*/
public static long factail(int number, long result) throws Exception {
if (number == 0) {
throw new Exception("result: " + result);
}
return factail(number - 1, result * number);
}
Of course, JVMs do not (like functional language interpreters or compilers) usually optimize for tail recursion, as the stack trace shows.
Sorry, forgot to add in the last post that you should call the auxiliary with result = 1.
public static long factorial(int number) throws Exception {
return factail(number, 1);
}
private static long factail(int number, long result) throws Exception {
if (number == 0) {
throw new Exception("result: " + result);
}
return factail(number - 1, result * number);
}
Indeed writing program to calculate factorial is good example for learning recursion. by the way is it tail recursive ?
At what point does this break down, because I've tested both methods incrementally up to 16 and they both give the same result (2004189184), but if you use 17 as the number then what you get back is a negative result, which cannot be correct (-288522240).
Why does this happen?
I think factorial program is not the best to understand recursion. The best way to understand recursion is to call a function twice i.e.
recursive()
{
System.out.println("Hello");
}
calling()
{
recursive();
recursive();
}
If you understand this then you probably know how recursion works.
I'd do it like this...
public static Integer factorial(int number) {
if (number == 1) {
System.out.println("Factorial ended");
return 1;
} else {
return number*factorial(number-1);
}
}
Could you write a program to calculate factorial but condition being you call the recursive function within a for loop
I do want to point out the question above regarding the negative result when retrieving the factorial for 17. This is because the primitive int is being used. To get around this then it is advised to use the BigInteger Object type.
Hi, I mean you can cache factorials instead of calculating again e.g. factorial(6) = 6* factorial(5), instead of calculating factorial(5), you can replace with 120. You can use any cache e.g. in memory, disk base or cloud based, upto you. simplest is a in memory HashMap cache.
Sorry, didn't get you. If you don't store already calculated value they will be lost, you need to memoization technique, which is also popular in calculating fibonacci series.
public class Fact{
public static void main(String[] args)
{
System.out.println(factorial(5));
}
public static int factorial(int n)
{
if(n==0||n==1)
return 1;
return factorial(n-1)*n;
}
}
public class Factorial {
public static void main(String[] args) {
int n = 7;
int result = 1;
for (int i = 1; i <= n; i++) {
result = result * i;
}
System.out.println("The factorial of 7 is " + result);
}
}
LongStream.range(1, factorialOf + 1).reduce(1, (a, b) -> a * b);
Hello pg7812, that's cool
Post a Comment