Factorial using Recursion in Java

How to Find Factorial Program in Java Using Recursion?

The definition of recursion is to call the function within itself. We can use this property and calculate the factorial of the number. Let us understand the process of finding factorial using recursion by an example.

Consider a number 5, now calculate the factorial of 5. In simple terms, we can write the factorial of 5 is the product of 5 and the factorial of $4 (5! = 4! × 5)$. Similarly, we can write:

$4! = 3! × 4$

$3! = 2! × 3$

$2! = 1! × 2$

And, the factorial of 1 is 1.

• To find the factorial of a number 5 we can call a recursive function and pass the number 5 within the factorial function.
• We will make a recursive call for calculating the factorial of number 4 until the number becomes 0, after the factorial of 4 is calculated we will simply return the value of $5 × 4!$.
• To calculate the factorial of 4 we will again call the recursive function. This process will continue until the number reaches 0.
• So, when the number reaches zero we will simply return 1 as the factorial of 0 is 1. The following pseudo-code will help you to understand the process of calculating the factorial.

Pseudo-Code

Let us implement the above pseudo-code in Java to find the factorial of any number N.

Code

Output

Time and Space Complexity

The time complexity of the above code is $O(N)$ because we call the recursive function N times. The space complexity of the above code is again $O(N)$ because the recursion stack takes $O(N)$ space in the internal memory.

As soon as we call the recursive function, the function call occupies space on the top of the call stack. The successive calls of the function within itself consecutively acquire space on top of each other in the call stack. We can understand the call stack by the following image.

When the method factorial() is called with argument equal to 0, the method returns the value 1, post which all the methods return the required values and get popped out from the call stack.

Iterative Method

In the iterative method:

• We will declare a variable res and initialize its value to 1.
• Now run a for loop from 1 to N. Every time we iterate in the loop multiply the res variable with the counter of the loop.
• Finally, after the execution of the loop result will be stored in the res variable.

Code

Output

Comparing Linear and Recursive Methods

Let us differentiate between the recursive and iterative method based on time and space complexities.

Comparing the time complexity of both methods we can say that both iterative and recursive methods take $O(N)$ time.

Difference lies in the space complexity

In terms of space complexity, the iterative method takes $O(1)$ space which is constant space whereas the recursive method takes $O(N)$ memory space. This is due to the $O(N)$ recursive method calls which acquire space order N space in the call stack.