Factorial in Java using Recursion and Loop

Problem : Write a program to calculate factorial of a given number in Java, using both recursion and iteration.

Solution : If you come from Maths background then you know that factorial of a number is number*(factorial of number -1). You will use this formula to calculate factorial in this  Java tutorial. Since factorial is a naturally recursive operation, it make sense to use recursion to solve this problem but its not always the best way. Iteration provides a more robust way, but don't worry you will learn how to calculate factorial with and without recursion in Java. By the way, factorial of numbers grows very quickly and even the largest integral data type in Java, long is not able to hold factorial of anything or above 50. In such cases you can use BigInteger, which has theoretically no limit and can be used to represent very large integral numbers.


Solution 1 : Factorial using recursion

In order to create a recursive solution you need a base case where program terminates and in this problem base case is factorial of 1, which is 1. So if given number is greater than 1, we keep applying factorial formula and recursive call this method with n - 1 as shown below :
 public static long factorial(int number){        
        //base case - factorial of 0 or 1 is 1
        if(number <=1){
            return 1;
        }        
        return number*factorial(number - 1);
    }
Once input become 1 the method stopped recursive call and return 1. From there onward stack started to roll down and finally factorial of number is calculated.




Solution 2 : Factorial without Recursion

As I said instead of using recursion and calling factorial method again you can also use for loop to calculate factorial because !n = n*(n-1)*(n-2).....*1 , which can easily be implemented using loop as shown below :
public static long factorial(long input){
        long factorial = 1L;
        for(long i= input; i > 0; i--){
            factorial = factorial * i;
        }
        
        return factorial;
    }
You can see that we start with the number and multiply it with the factorial which is initialized with 1 then we reduce the number by 1 until number becomes 1, which is nothing but n*(n-1)*(n-2).....*1.

How to calculate factorial in Java using recursion



Java Program to calculate Factorial with and without Recursion

Here is our complete solution of this problem. You can see that I have created two factorial() method, one accept int and return long e.g. long factorial(int number), while other accept a long and return a long factorial i.e. long factorial(long number). Since their parameter type is different they are two different method also known as overloaded methods. First method uses recursion to calculate factorial while second method uses iteration to calculate factorial.

import java.math.BigInteger;
import java.util.Calendar;
import java.util.Date;
import java.util.GregorianCalendar;

/**
 * Java Program to calculate factorial using iteration and recursion
 * 
 * @author WINDOWS 8
 *
 */
public class FactorialTest {

    public static void main(String args[]) {
       
        System.out.println("factorial of 1 using recursion : " + factorial(1));
        System.out.println("factorial of 1 using iteration : " + factorial(1L));
        
        System.out.println("factorial of 5 using recursion : " + factorial(5));
        System.out.println("factorial of 5 using loop : "   + factorial(5L));       
        
        System.out.println("factorial of 7 using recursive algorithm : " + factorial(7));
        System.out.println("factorial of 7 using iterative algorithm : " + factorial(7L)); 
        
    }

  
    /**
     * Java method to calculate factorial of given integer using recursion.
     * @param number
     * @return factorial of number
     */
    public static long factorial(int number){
        
        //base case - factorial of 0 or 1 is 1
        if(number <=1){
            return 1;
        }
        
        return number*factorial(number - 1);
    }
    
    /**
     * Java method to calculate factorial of given number using iteration
     * @param input
     * @return factorial of input
     */
    public static long factorial(long input){
        long factorial = 1L;
        for(long i= input; i > 0; i--){
            factorial = factorial * i;
        }
        
        return factorial;
    }
    
}

Output :
factorial of 1 using recursion : 1
factorial of 1 using iteration : 1
factorial of 5 using recursion : 120
factorial of 5 using loop : 120
factorial of 7 using recursive algorithm : 5040
factorial of 7 using iterative algorithm : 5040


That's all about how to calculate factorial of a number in Java using both recursion and iteration. This problem is often used to teach programming, particularly recursion in school and colleges and its good one as well. Just remember that even though recursive solution are small and clear they are prone to throw StackOverFlowException, hence not suitable for production code. Iteration or use of for loop results in more robust solution.

If you are learning programming then you can also try following problem to improve your logic and coding skill :
  • How to check if a given number is prime or not? (solution)
  • How to find if given String is palindrome in Java? (solution)
  • How to reverse an int variable in Java? (solution)
  • How do you swap two integers without using temporary variable? (solution)
  • Write a program to check if a number is power of two or not? (solution)
  • How to reverse String in Java without using StringBuffer? (solution)
  • How do you reverse word of a sentence in Java? (solution)
  • How to find a missing number in a sorted array? (solution)

No comments:

Post a Comment