## 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 callsOne 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:
## 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. |