Monday, September 7, 2015

Different ways of calculating Factorial in java

Problem : Write a program to calculate factorial of a given number in Java.

Explanation: 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.

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.
We can calculate Factorial by following 3 ways:

  1. Using recursion 
  2. Using Loop
  3. Using Dynamic Programming.
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.

Example:
import java.util.Scanner;

/** Java Program to calculate factorial using loop
 *
 * @author RD 
 * 
 **/

public class Factorial {

   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       System.out.print("Enter the number whose factorial is to be found: ");
       int n = scanner.nextInt();
       int result = factorial(n);
       System.out.println("The factorial of " + n + " is " + result);
   }

   public static int factorial(int n) {
       int result = 1;
       for (int i = 1; i <= n; i++) {
           result = result * i;
       }
       return result;
   }
}


Solution 2 : Factorial using loop
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.  
Why we use Recursion in methods? 

  1. Code is easier to read 
  2. Less lines of code
  3. Problem solving approach is somewhat divide and conquer: Solve bigger problem by solving simpler sub problems.
Example
/**
  * Java Factorial Using Recursion Example
  * This Java example shows how to generate factorial of a given number using recursive function.
  * @author RD
**/
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class JavaFactorialUsingRecursion {
       
        public static void main(String args[]) throws NumberFormatException, IOException{
               
                System.out.println("Enter the number: ");
               
                //get input from the user
                BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
                int a = Integer.parseInt(br.readLine());
               
                //call the recursive function to generate factorial
                int result= fact(a);
               
               
                System.out.println("Factorial of the number is: " + result);
        }
       
        static int fact(int b)
        {
                if(b <= 1)
                        //if the number is 1 then return 1
                        return 1;
                else
                        //else call the same function with the value - 1
                        return b * fact(b-1);
        }
}

Solution 3 : Factorial using dynamic programming

Dynamic Programming is similar to Recursion in which we break the problem into subproblems and use them to arrive at the final solution. However, it is different from Recursion as we store results of already solved subproblems to avoid re- calculation. Caching of results leads to better time complexity of code at the cost of space complexity.



public static long factorial(int n)
{
    if (n >= 0) 
    {
        result[0] = 1;
        for (int i = 1; i <= n; ++i) 
        {
            result[i] = i * result[i - 1];
        }
        return result[n];
    }
}
Dynamic Programming approach will be caching the solved sub problems and will be more efficiently execute in linear time.

No comments:

Post a Comment

Java garbage collection

In this post , we ’ ll take a look at how garbage collection works , why it ’ s important in Java , and how it works in...