Nikos Maravitsas

About Nikos Maravitsas

Nikos has graduated from the Department of Informatics and Telecommunications of The National and Kapodistrian University of Athens. Currently, his main interests are system’s security, parallel systems, artificial intelligence, operating systems, system programming, telecommunications, web applications, human – machine interaction and mobile development.

Factorial Program in Java

In this example we are going to talk about a classic programming task, as we are going to create a Java program that computes the factorial of a non negative integer. Those of you who know your math, you should already know:

The factorial of a positive integer n, annotated n!, is the product of all positive integers from 1 to n. Also, 0! = 1

Hence n! = 1*2*3*4*5.....*n. And so 4! = 1*2*3*4 = 24. Pretty simple.
 
 
 

1. A simple for-loop calculation

This is the most straight forward implementation you can do to calculate the factorial of a non negative integer.

MathUtils.java:

package com.javacodegeeks.core.factorial;

public class MathUtils {

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

This program is really self explanatory. We simply loop from 1 to n, adding the respectful number to the product at each iteration.

Let’s use this utility method in a simple program :

FactorialExample.java:

package com.javacodegeeks.core.factorial;

public class FactorialExample {
	public static void main(String[] args){	
		System.out.println(MathUtils.simpleFactorial(10));
	}
}

If you run the program, this is the output:

3628800

2. A recursive solution

There is no particular reason why you shouldn’t use the above simple for-loop implementation. In fact it’s the fastest one of those listed in this post. The reason is simply because it doesn’t use the call stack to hold the intermediate products, as recursive solutions do. But for the shake of completeness, we will provide recursive solutions as well. Having said that, you might find the following implementations handy in interview ventures.

MathUtils.java:

package com.javacodegeeks.core.factorial;

public class MathUtils {
	
	public static int recurciveFact(int n){
		if(n == 0){
			return 1;
		}else{
			return n*recurciveFact(n-1);
		}
	}
}

Let’s break down the above method. Let’s, for example calculate 4!.

recurciveFact(4) = 4*recurciveFact(3) 
    recurciveFact(3) = 3*recurciveFact(2) 
        recurciveFact(2) = 2*recurciveFact(1) 

              recurciveFact(1) = 1*recurciveFact(0) =1*1 =1
                             
         recurciveFact(2) = 2*recurciveFact(1) = 2*1 = 2 
    recurciveFact(3) = 3*recurciveFact(2) = 3*2 = 6 
recurciveFact(4) = 4*recurciveFact(3) = 4*6 = 24 

This is how recursion works in this case. So as you can see the intermediate example are calculated an stored in the call stack.

3. A tail-recursive solution

Tail recursion is a technique dictating that : There is nothing to do after the function returns except return its value.

MathUtils.java:

package com.javacodegeeks.core.factorial;

public class MathUtils {

	public static int tailrecurciveFact(int n){
		return factorial(n,1);
	}
	
	private static int factorial(int n,int accum){
		if(n==0)
			return accum;
		else{
			return factorial(n-1,n*accum);
		}
	}
}

Let’s break down the calculatation 4!, so you can clearly see the case to support tail recursion.

tailrecurciveFact(4) = factorial(4,1)
   factorial(4,1) =  factorial(3,4*1)
      factorial(3,4*1) =  factorial(2,4*1*3)
          factorial(2,4*1*) =  factorial(1,4*1*3*2)
  
             factorial(1,4*1*3*2) =  factorial(0,4*1*3*2*1) = 24

          factorial(2,4*1*) = 24
      factorial(3,4*1) = 24
   factorial(4,1) = 24
tailrecurciveFact(4) = 24;

As you can see the final result is already calculated as the algorithm descends in the call stack. So when the program returns, the result is already calculated and no more calculations are performed. Using this method, one can easily implement optimizations for what is the major problem with recursion: space . For example, one could use only the deeper stack frame to hold the result and immediately return the result of tailrecurciveFact(4).

Several compilers implement different straightforward optimizations by flattening the tail recursion to a simple while loop. First you can imagine that the program could be transformed in the following pseudo-code (as goto is not implemented in Java):

private static int factorialGoto(int n,int accum){
	loop:
	if(n==0)
		return accum;
	else{
		accum*=n;
		n -= 1;
		goto loop;
	}
}

It’s trivial to flatten this to a single while loop :

private static int factorialWhile(int n,int accum){
	while (n != 0) {
		accum *= n;
		n -= 1;
    }
	return accum;
}

So you can see how tail recursion can be used to help the compiler produce really fast code, and on the same time you can keep using recursion, if you are having fun with functional programming. It is important to note though, that not all recursive programs can be transformed to tail recursive.

Download Source Code

This was an example about factorial Program in Java. You can download the source code of this example here : FactorialExample.zip

Related Whitepaper:

Java Essential Training

Author David Gassner explores Java SE (Standard Edition), the language used to build mobile apps for Android devices, enterprise server applications, and more!

The course demonstrates how to install both Java and the Eclipse IDE and dives into the particulars of programming. The course also explains the fundamentals of Java, from creating simple variables, assigning values, and declaring methods to working with strings, arrays, and subclasses; reading and writing to text files; and implementing object oriented programming concepts. Exercise files are included with the course.

Get it Now!  

Examples Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy
All trademarks and registered trademarks appearing on Examples Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Examples Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.

Sign up for our Newsletter

20,709 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books