Write a function that, given a number as input, returns the factorial of that number. The factorial of a number ‘n’ is the product of all positive integers less than or equal to ‘n’. So, the factorial of 6 would be 6*5*4*3*2*1 = 720. The factorial of 0 is 1.

 

This question was asked during an interview with NCR.

The factorial for a number ‘n’ would be n*(n-1)*(n-2)…*1. Problems like this that have a repetitive pattern tend to be more easily solved by using recursion.

Taking a closer look at the problem, we could also say that the factorial of a number ‘n’ is also equivalent to the number ‘n’ multiplied by the factorial of ‘n-1’. With that in mind, we can write the following recursive Java method:

Java Factorial in Recursion:

public int Factorial(int n)
{
	return n * Factorial(n-1);
}

Boundary conditions in recursion prevent infinite function calls

One thing is obviously missing from the code above. If we were to pass in a number, then the function simply will not stop executing! We need to add a boundary condition, but what should it be? Because factorials are only defined for non negative integers, it makes sense to use 0 as our boundary case. So, if ‘n’ (the number passed in to the function) ever equals 0 then we will return a 1, because the factorial of 0 is 1. Now, we have this:

public int Factorial(int n)
{
	if (n == 0)
		return 1;
	else
		return n * Factorial(n-1);
}

Using iteration and a loop in Java to calculate the factorial instead of recursion




Although we presented the recursive answer to the question above, using recursion is not the best solution to the problem – especially when you are dealing with very large numbers. For instance, if you are trying to calculate the factorial of a large number like 1,000,000 then you could very well end up with a stack overflow issue – because of the large amount of memory required by too many recursive calls as you can read about here: Example of Recursion. So, iteration is the better solution for this problem. Here is what the iterative solution looks like in Java:

Java Factorial iteration – using a for loop:

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;

  return fact;

}

We’ve now found our answer – all that work and the code is suprisingly simple! This question is a favorite for interviewers, and it’s a good idea to know both the iterative and recursive solutions.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • Sohail Rizwan

    Iterative one is better in any case, but lets say, you’ve very small number like less than 10, then recursive would be fast and better.

  • Ferhan Jamal

    I am learning recursion and iteration method in programming these days. I have written a code by the above two methods to calculate the factorial of a number. I just want to know that which method has the better approach and why ?